Binary Search

Basic Algorithm

Given: An array sorted in ascending order

Complexity: O(Log n)

Recursive Algorithm:

Iterative Algorithm:

Points to note

1. l≤r : we need to keep halving the array , until we have one element and narrow down the search space to a single element
2. We consider mid, mid-1 and mid+1 elements

Upper Bound

C++ shortcut

• Lets assume the following as the input

10 10 10 20 20 20 30 30

C++ syntax : upper_bound (v.begin(), v.end(), 20)

The above statement will return index 6 . It basically returns the index post the last index where our target element was present

int binsrch(vector<int> &arr,int &target)
{
  int l=0, r=arr.size()-1,ans=0;
  
  while(l<=r)
  {
    int mid = l+ (r-l)/2;
    if(a[mid]>=target)
    {
      l=mid+1;
    }
    else
     {
        ans=mid;
        r=mid-1;
     }
   }

  return ans;
}

Points to note:

• l<r , since the condition r=mid does not decrement mid and we do not end up with a condition where l>r unlike the previous case and we break the loop when l=r
• r=mid since we need to include the index where the element was found and keep narrowing down further
• The index l returned gives us the upper bound

Lower Bound

C++ syntax : lower_bound (v.begin(), v.end(), 20)

Input : 10 10 10 20 20 20 30 30

The above statement return the value 3 which is the first index where 20 was found.

int binsrch(vector<int> &arr,int &target)
{
  int l=0, r=arr.size()-1,ans=0;
  
  while(l<=r)
  {
    int mid = l+ (r-l)/2;
    if(a[mid]>=target)
    {
      r=mid-1;
    }
    else
     {
        ans=l;
        l=mid+1;
     }
   }

  return ans;
}

Points to note:

• We return l as the previous case
• In this case the condition to check would be if(arr[mid]≤target)

Binary Search Practice Questions