Binary Search on 1D Array

Introduction
In Binary Search the array need to be sorted.

Then take two pointers, low pointer at index-0 and high pointer at index n-1

Find the mid element, mid = (low + high)/2

Pseudocode

Iterative Method
 int search(vector<int> &nums, int target) { cpp
int n = nums.size();
int low = 0;
int high = n-1;

while(low <= high){

// if overflow occurs, then take int mid = low + (high - low) / 2;
int mid = (low+high)/2;

if(nums[mid] == target) return mid;

else if(target < nums[mid]) high = mid - 1;

else{
low = mid + 1;
}
}

return -1;

Recursive Method
int bs(vector<int> &arr, int low, int high, int target){ cpp

if(low > high) return -1;

// if overflow occurs, then take int mid = low + (high - low) / 2;
int mid = (low+high)/2;

if(arr[mid] == target) return mid;

else if(target > arr[mid]) return bs(arr,mid+1,high,target);
else return bs(arr,low,mid-1,target);
}

int search(vector<int> &nums, int target) {

int n = nums.size();
return bs(nums,0,n-1,target);

Dry Run
Time Complexity
Worst Case - O(logn)

BS-2. Implement Lower Bound and Upper

Bound

Lower Bound
 Here for cases like x = 20(which is not present in the array) it will return lower
bound as 5(which is the size of the array)

And for x = 15, lower bound = 4(index 19)

for x = 19, lower bound = 4(index of 19)

int lowerBound(vector<int> arr, int n, int x) { cpp

int ans = arr.size();
int low = 0;
int high = n-1;

while(low <= high){

//may be an answer
int mid = (low+high)/2;
if(arr[mid] >= x){
ans = mid;
//look for more small intdex on left
high = mid - 1;
}
else{
low = mid+1;//look for right
}
}
return ans;
}

Here we have to find the arr[mid] such that arr[mid] >= x then we have to
find the smallest arr[mid] in the left half such that arr[mid] >=x

Using C++ STL :

int lowerBound(vector<int> arr, int n, int x) { cpp

int ans = lower_bound(arr.begin(),arr.end(),x) - arr.begin();

return ans;
}

Upper Bound
 It is similar to lower bound but the condition will be arr[index] > x

int upperBound(vector<int> &arr, int x, int n){ cpp

int ans = arr.size();
int low = 0;
int high = n-1;

while(low <= high){

//may be an answer
int mid = (low+high)/2;
if(arr[mid] > x){
ans = mid;
//look for more small intdex on left
high = mid - 1;
}
else{
low = mid+1;//look for right
}
}
return ans;
}

Using C++ STL :

int lowerBound(vector<int> arr, int n, int x) {

int ans = upper_bound(arr.begin(),arr.end(),x) - arr.begin();

return ans;
}

BS-2. Search Insert Position

Its implementation is exactly same as lower bound

 class Solution { cpp
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int ans = n;
int low = 0;
int high = n-1;

while(low <= high){

int mid = low + (high - low)/2;

if(nums[mid]>=target){
ans = mid;
high = mid -1;
}

else{
low = mid+1;
}
}
return ans;
}
};

BS-2. Floor/ceil in sorted array

For ceil, logic is same as lower bound .

But for floor, you have to find the arr[mid] such that arr[mid] <= x , then we
have to look for the largest arr[mid] in the right half such that arr[mid] <= x.

int floor(vector<int> &arr, int n, int x) { cpp

int ans1 = -1; // Initialize answer to -1
int low = 0;
int high = n - 1;

while (low <= high) {

int mid = (low + high) / 2; // Calculate the middle index

if (arr[mid] <= x) {
ans1 = arr[mid]; // Update answer to the current mid value
low = mid + 1; // Move to the right half
} else {
high = mid - 1; // Move to the left half
}
}
return ans1; // Return the final answer (floor value)
}

// Function to find the ceiling of x in a sorted array

int ceil(vector<int> &arr, int n, int x) {
int ans2 = -1; // Initialize answer to -1
int low = 0;
int high = n - 1;

while (low <= high) {

int mid = (low + high) / 2; // Calculate the middle index

if (arr[mid] >= x) {
ans2 = arr[mid]; // Update answer to the current mid value
high = mid - 1; // Move to the left half
} else {
 low = mid + 1; // Move to the right half
}
}
return ans2; // Return the final answer (ceiling value)
}

vector<int> getFloorAndCeil(int x, vector<int> &arr) {

int n = arr.size();
sort(arr.begin(),arr.end());
vector<int> ans;
int f = floor(arr, n, x);
int c = ceil(arr, n, x);
ans.push_back(f);
ans.push_back(c);
return ans;
}

BS-3. First and Last Occurrences in an

array

Using Lower Bound and Upper Bound method

To find the first occurrence you can use the concept of lower bound
To find the last occurrence you can use the concept of upper bound such that
(Last occurrence = Upper Bound - 1)

If (array[lower bound] != target) return {-1,-1}

int lowerBound(vector<int> arr, int n, int x) { cpp

int ans = n;
int low = 0;
int high = n-1;

while(low <= high){

//may be an answer
int mid = (low+high)/2;
if(arr[mid] >= x){
ans = mid;
//look for more small intdex on left
high = mid - 1;
}
else{
low = mid+1;//look for right
}
}
return ans;
}

int upperBound(vector<int> &arr, int n, int x){

int ans = n;
int low = 0;
int high = n-1;

while(low <= high){

//may be an answer
int mid = (low+high)/2;
if(arr[mid] > x){
ans = mid;
//look for more small intdex on left
high = mid - 1;
}
else{
low = mid+1;//look for right
}
}
return ans;
}

pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)

{
int lb = lowerBound(arr,n,k);

if(lb == n || arr[lb] != k) return {-1,-1};

 return {lb, upperBound(arr, n, k) - 1};
}

Using Binary Search Method

First occurrence:

int firstOccur(vector<int> arr, int n, int x) { cpp

int first = -1;
int low = 0;
int high = n-1;

while(low <= high){

int mid = (low+high)/2;
if(arr[mid] == x){ // Since target is equal to arr[mid] look for more tagets in the lef
t
first = mid;
high = mid - 1;
}
else if(arr[mid] < x){// since arr[mid] is smaller than target,look in the right half f
or the target
low = mid+1;
}
else{
high = mid - 1; // since arr[mid] is bigger than target,look in the left half for t
he target.
}
}
return first;
}

Last occurrence:

int lastOccur(vector<int> &arr, int n, int x){ cpp

int last = -1;
int low = 0;
int high = n-1;

while(low <= high){

int mid = (low+high)/2;
if(arr[mid] == x){ // Since target is equal to arr[mid] ,look for more tagets in the ri
ght
last = mid;
low = mid + 1;
}
 else if(arr[mid] < x){
low = mid+1;// since arr[mid] is smaller than target,look in the right half for the
target
}

else{
high = mid - 1; // since arr[mid] is bigger than target,look in the left half for t
he target.
}
}
return last;
}

Calling the functions:

pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k) cpp

{
int first = firstOccur(arr,n,k);

if(first == -1) return {-1,-1};

int last = lastOccur(arr,n,k);
return {first,last};
}

BS-4. Search element in rotated sorted

array

Here target = 1 and we have to return the index of 1 which is 3

At first, find the mid if arr[mid] ==target then return mid

Then, check if arr[low] to arr[mid] is sorted , if yes,

check if target is present between arr[low] to arr[mid],if present

eliminate the right half

 else eliminate the left half

Or, if arr[mid] to arr[high] is sorted

check if target is present between arr[high] to arr[high],if present

eliminate the left half

else eliminate the right half

Note : Identify the sorted half

class Solution { cpp

public:
int search(vector<int>& nums, int target) {

int n = nums.size();
int low = 0;
int high = n - 1;

while(low <= high){

int mid = (low + high)/2;

if(nums[mid] == target){
return mid;
}

else if(nums[low] <= nums[mid]){

if(nums[low] <= target && target <= nums[mid]){
high = mid - 1;
}
else {
low = mid + 1;
}
}

else{
if(nums[mid] <= target && target <= nums[high]){
low = mid + +1;
}
else{
high = mid - 1;
}
}
}
return -1;
}
};
BS-5. Search element in rotated sorted
array-II

(Array may contain duplicate elements)

The edge case which causing the problem is --

If arr[low] == arr[mid] == arr[high]

To solve this edge case, trim down the search space-

To trim down the search space use the below code in the previous program

if(nums[low] == nums[mid] && nums[mid] == nums[high]){ cpp

low++;
high--;
continue;
}
class Solution { cpp
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
int low = 0;
int high = n - 1;

while(low <= high){

int mid = (low + high)/2;

if(nums[mid] == target){
return true;
}

if(nums[low] == nums[mid] && nums[mid] == nums[high]){ // code to trim down the sea
rch space
low++;
high--;
continue; //Here continue is used as more nums[low] = nums[mid] = nums[high] c
ould present
}

else if(nums[low] <= nums[mid]){

if(nums[low] <= target && target <= nums[mid]){
high = mid - 1;
}
else {
low = mid + 1;
}
}

else{
if(nums[mid] <= target && target <= nums[high]){
low = mid + +1;
}
else{
high = mid - 1;
}
}
}
 return false;
}
};

continue; is used for the below condition

BS-6. Minimum in rotated sorted array

To find the minimum element in the rotated sorted array

At first, we have to find the sorted half and find the minimum and eliminate
the sorted half

If the left half is sorted, the minimum element will be arr[low] and then
eliminate the left half

else the right half is sorted, the minimum element will be arr[mid] and then
eliminate the right half
 class Solution { cpp
public:
int findMin(vector<int>& nums) {
int n = nums.size();

int low = 0;
int high = n - 1;
int ans = INT_MAX;

while(low <= high){

int mid = (low + high)/2;
if(nums[low] <= nums[mid]){
ans = min(ans,nums[low]); // Minimum in the left sorted half
low = mid + 1; // Eliminate the left sorted half
}
else{
ans = min(ans,nums[mid]); // Minimum in the right sorted half
high = mid - 1; // Eliminate the right sorted half
}
}
return ans;
}
};

You can optimize the solution(if you want): If both left and right half are sorted

If search space is already sorted then always arr[low] will be smaller in that
search space
 class Solution { cpp
public:
int findMin(vector<int>& nums) {
int n = nums.size();

int low = 0;
int high = n - 1;
int ans = INT_MAX;

while(low <= high){

int mid = (low + high)/2;
if(nums[low] <= nums[high]){ //if search space is already sorted then always arr[l
ow] will be smaller
ans = min(ans,nums[low]); // in that search space
break;
}

if(nums[low] <= nums[mid]){

ans = min(ans,nums[low]);
low = mid + 1;
}
else{
ans = min(ans,nums[mid]);
high = mid - 1;
}
}
return ans;
}
};

BS-7. Find the how many times array has

been rotated
(similar to previous problem)

It is similar to the previous problem where we have to return the index of the
minimum element in the rotated sorted array

int findKRotation(vector<int> &arr) { cpp

int n = arr.size();

int low = 0;
int high = n - 1;

int index = -1;// Here we to take a index variable

int ans = INT_MAX;

while(low <= high){

int mid = (low + high)/2;
if(arr[low] <= arr[high]){
if(arr[low] < ans){
ans = arr[low];
}
index = low;
break;
}

if(arr[low] <= arr[mid]){

if(arr[low] < ans){
ans = arr[low];
index = low;
}
low = mid + 1;
}
else{
if(arr[mid] < ans){
ans = arr[mid];
index = mid;
}
high = mid - 1;
}
}
 return index;
}

BS-8. Single element in a sorted array

To solve this problem here we to find out which half of the element are we in

To understand which half of the element are we in you can visualize it through
the below image

If we are in the left half, we will eliminate the left half

if the index of mid is odd and arr[mid] == arr[mid] or index of mid is even
and arr[mid] == arr[mid+1] then we are in the left half and to eliminate the
left half use low = mid +1
 else we are in the right part, we will eliminate the right part using high = mid - 1

We have to also consider some edge case:

If array length is 1 return arr[0]

If arr[0] != arr[1] return arr[0]

If arr[n-1] != arr[n-2] return arr[n-1]

And we will keep the low pointer at index-1 and high pointer at index n-2 so
that we can cover up the case of if(arr[mid] != arr[mid-1] && arr[mid] !=
arr[mid+1] return arr[mid]

class Solution { cpp

public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size();

int low = 1;
int high = n - 2;
if (n == 1)
return nums[0];
if (nums[0] != nums[1])
return nums[0];
if (nums[n - 1] != nums[n - 2])
return nums[n - 1];

while (low <= high) {

int mid = (low + high) / 2;

if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {

 return nums[mid];
}
// We are in the left half of the element, so eliminate the right half
else if ((mid % 2 == 1 && nums[mid] == nums[mid - 1]) ||
(mid % 2 == 0 && nums[mid] == nums[mid + 1])) {
low = mid + 1;
}
// We are in the right half of the element ,so eliminate th right half
else {
high = mid - 1;
}
}
return -1;
}
};

BS-9. Find Peak Element

If arr[mid] > arr[mid - 1] && arr[mid] > arr[mid+1] then return the mid

To solve this problem we have to identify which half of the peak are we in

If arr[mid] > arr[mid-1] we(mid) are in the increasing half so eliminate that
half

If arr[mid] > arr[mid+1] we(mid) are in the decreasing half so eliminate that
half
We have to also consider some edge case:

If array length is 1 return 0

If arr[0] > arr[1] return 0

If arr[n-1] > arr[n-2] return n-1

we consider the last two edge cases so that we can kept the low pointer at index-
1 and high pointer at index- n-1

To cover the below edge case where arr[mid-1] > arr[mid] < arr[mid+1] we
will use the else condition as low = mid + 1 or high = mid -1 as the peak can
present in both halfs so we eliminate any half

class Solution { cpp

public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
if(n==1) return 0;
if(nums[0] > nums[1]) return 0;
if(nums[n-1] > nums[n-2]) return n-1;

int low = 1;
int high = n-2;

while(low <= high){

int mid = (low+high)/2;
if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid+1]){
return mid;
}
else if(nums[mid] > nums[mid-1]){
low = mid + 1;
}
else if(nums[mid] > nums[mid + 1]){
high = mid - 1;
}
else{
low = mid + 1;
}
}
return -1;
}
};