Binary Search

Note : In coding rounds, always use mid= low+(high-low)/2 instead of (low+high)/2 to pass 2 critical test cases else overflow error comes (they genuinely add these cases to test your coding skills

You use while (start <= end) if you are returning the match from inside the loop.

You use while (start < end) if you want to exit out of the loop first, and then use the result of start or end to return the match.

must read comments on this blog

STL binary seach : leetcode post

Calculating n-th root of a no using binary search

Here let guessed ans = mid*mid*mid*…n times

We check if difference of (guessed ans-given no) is less or greater than the accuracy we want then according to that do binary search

double getNthRoot(int n, int m) {
    double low = 1;
    double high = m;
    double eps =0.00000001; // 0.0000001 (accuracy)
    double mid=(low+high)/2;
    while(abs((pow(mid,n))-m) >= eps) {
        if(pow(mid,n) < m)
        low=mid;
        else high=mid;
        mid=(low+high)/2;
    }
    
    cout << mid << endl;
}

OR

double getNthRoot(int n, int m) {
    double low = 1;
    double high = m;
    double eps = 0.0000006 
    
    while((high - low) > eps) {
        double mid = (low + high) / 2.0; 
        if(pow(mid, n) < m) 
            low = mid; 
        else 
            high = mid; 
    }
// print any one low or high since 
// low=high upto 0.0000006 accuracy only after that they will differ
    cout << low << " " << high << endl; 
    
// just to check our ans
   cout << pow(m, (double)(1.0/(double)n));

Time complexity analysis :

For upto 1 place of decimal 1.1, 1.2, 1.3….2 ….2.1,2.2,2.3,….. upto M so (M*10)

For upto d places of decimal it is 10^d i.e 10 to the power d so M*10^d

Since We are doing binary search i.e skipping half iterations everytime so overall time complexity is : log (M* (10^d) )

Also pow(m , N) does m*m*m….. N times so O(N) so overall time is :

N * log(M* (10^d) )

Median in a row-wise sorted Matrix

We are given a row-wise sorted matrix of size r*c, we need to find the median of the matrix given. It is assumed that r*c is always odd.

The Brute force is that we would spread out the whole matrix and store it in an array and after that we would sort that array and check the middle of the array. Time : O((M * N) * log(M * N)) as M*N elements are there and we are sorting so nlogn or M*Nlog(M*N)

Optimal method → binary search

• Now since there are odd elements in total , median is always present at (no of elements/2) i.e (M*N)/2 th position .Also we know that for a median there are n/2 elements to its left & n/2 to its right ( n is odd GIVEN)
• we know that for a number to be median there should be exactly (n/2) numbers which are less than this number. So, we try to find the count of numbers less than equal all the numbers (using binary search)
• initially low=min element in matrix & high=max element in matrix so as to cover the entire search space
• keep in mind that our desired position is (M*N)/2 so if we count no of elements lesser than or equal to mid and if the count is ≤ (M*N)/2 that means we need to go right so low=mid + 1 else if count>(M*N)/2 then we need go to the left so high=mid-1
• Keep in mind that we need such a count that there are half elements in left & half elements in right so the moment low crosses high that would surely be the median (dry run and understand)
• To count no of elements ≤ mid we again do binary search see this pic below to know how we do it (We could have used upper_bound(matrix[i], matrix[i]+c, mid) — matrix[i] but not allowed in interviews)

int countSmallerThanEqualMid(vector<int> &row, int mid) {
    int l = 0, h = row.size() - 1; 
    while(l <= h) {
        int md = (l + h) >> 1; 
        if(row[md] <= mid)
            l = md + 1;
        else 
            h = md - 1;
    }
    return l; 
}
int findMedian(vector<vector<int> > &A) {
    int low = INT_MIN;
    int high = INT_MAX; 
    int r = A.size();
    int c = A[0].size(); 
    while(low <= high) {
        int mid = (low + high) >> 1; 
        int cnt = 0;
        for(int i = 0;i<r;i++) {
            cnt += countSmallerThanEqualMid(A[i], mid); 
        }
        
        if(cnt <= (r * c) / 2) low = mid + 1; 
        else high = mid - 1; 
    }
    return low; 
}

Time complexity analaysis

O(32 * M * log(N)), where ‘M’ denotes the number of rows and N denotes the number of columns of the matrix.

We do binary search from min to max ….min is 1 and max can be 32 bits long

Since the maximum number in the matrix can be of 32 bits long so the worst case will be that we will search from 1 to 2 ^ 32 so in the worst case binary search will run at most log(2 ^ 32) = 32 times and we are searching for count in each row (total M rows) also using binary search that will given us O(M * log(N)). Thus, the total time complexity will be O(M)(for finding min and max numbers) + 32 * O(M * log(N)) = O(32 * M * log(N))

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once ( in log N time)

Here see this blog

Search in Rotated Sorted Array

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

see here leetcode(link)

Median of 2 sorted array of diff size in

Time should be log ( min (M,N) ) time

Here

K-th element of two sorted Arrays

Time should be log ( min (M,N) ) time

similar question as above Here

Note :

In easy questions we are given a sorted array & we do binary search but in tricky hard problems like min page allocation, worker overload etc. we need to think out of box and decide the search space which is monotonically increasing i.e. sorted in such questions we take at least X for each Y and then find sum and if sum exceeds X we do required ++ and if required==required given it is a possible Ans and then we try to min/max it according to the question

Allocate min no pages problem

similar to the above 2 questions

here

Aggressive Cows exactly similar to min no of pages problem

Here best blog by me ( MUST READ )

FairWorkLoad Porblem (description)

(division 1 problem SRM 169 very tough (for people not for me xD )….exactly similar to above problem (here is the solution) easyyyyyy

some more easy questions

Binary Search on Reverse Sorted Array(decreasing order)

if target < mid then instead of left search for right half & vice versa

Order not know (ascending/descending) binary search

just compare 1st and last element to determine ascending / descending & then procees accordingly

First and Last occurrence of an Element

do 2 binary searches as usual and for 1st occurence if key is found at mid then store the mid somewhere and do high=mid-1 instead of returning and rest as usual

Similarly for last occurrence if key found at mid then store it & do low=mid+1 rest code same

Count of an Element in a Sorted Array

see all 3 approaches from worst to best here

Rotated Sorted Array problems

Always keep in mind low≤high means our ans will be inside the loop and low<high means our ans will be outside the loop

Find the no of times a rotated sorted array is sorted (here)

find the index of the mi element in a rotated sorted array (here )

Search in Rotated Sorted Array (Here)

Search in an almost sorted array

Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1]

OR

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2 
Output is index of 40 in given array

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
-1 is returned to indicate element is not present

Appraoch :

Instead of just comparing with A[mid], we compare with A[mid-1], A[mid], and A[mid+1], where if found great else we go to left/right half depending on mid whether its larger/smaller than target

int searchElement(int A[], int n, int x) {
  int low = 0, high = n - 1;
while (low <= high) {
    int mid = (low + high) / 2;
if (A[mid] == x)
      return mid;
if (mid - 1 >= low && A[mid - 1] == x)
      return mid - 1;
if (mid + 1 <= high && A[mid + 1] == x)
      return mid + 1;
else if (x > A[mid])
      low = mid + 2;
else
      high = mid - 2;
  }
  return -1;
}

Find Floor of an element in a Sorted Array

Floor of X is the greatest element that is ≤ X . Do usual binary search if X is found at mid then simpy return else when element at mid is < X then just update ans to arr[mid] before calling right half

int findFloor(vector<long long> v, long long n, long long x){
        
        int ans=-1;
        int low=0,high=n-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(v[mid]==x) return mid;
            else if(v[mid]<x)
            {
                ans=mid; 
         // this ans gets updated everytime v[mid]<x so we 
         // eventually get the greatest element        
                low=mid+1;
            }
            else high=mid-1;
        }
        return ans;

Find Ceil of an element in a Sorted Array

Ceil of X is the smallest element ≥ X so exactly the same code as above just update the ans when v[mid] > x instead of v[mid] < x

Next Alphabetical Element

Here

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order (here)

int find_index(int arr[], int n, int K)
{
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == K)
            return mid;
        else if (arr[mid] < K)
            start = mid + 1;
        else
            end = mid - 1;
    }
    return start;
}

Find position of an element in an Infinite Sorted Array

gfg article best

This problem cannot be made in a compiler it is a famous interview problem now low will be 1st element but we dont know where high will go so we take high=2nd element and if this range includes target perform binary search else increase high to 2*high and the previous high becomes the new low continue doing so till we found the cover the target

Now time complexity is time taken to find position ‘p’ of the target and since we are doing high=2*high everytime so Log(p) now once target is included range we do binary search so again log(p)… total time is O(logp)

First give brute force that we’ll one by one take every element and include that in range & then do binary search O(N + logp) & then say instead of linearly we can find the high using high=2*high so O(logP + logP)

int findPos(int arr[], int key){
int low = 0, high = 1;
int val = arr[0];
while (val < key)
{
low = high;        // store previous high
high = 2*high;      // double high index
val = arr[high]; // update new val
}
return binarySearch(arr, low, high, key);
}

Index of First 1 in a Binary Sorted Infinite Array

Just keep increasing high like in the above question till the range low to high includes your target ‘1’ and then find the 1st occurence of ‘1’

Above question was infine sorted + simple binary search of target

this question is infinite sorted + simple 1st occurence of target i.e ‘1’

int findPos(int arr[]){
int low = 0, high = 1;
int val = arr[0];
while (val < 1)   // in place of key we have 1
{
low = high;        // store previous high
high = 2*high;      // double high index
val = arr[high]; // update new val
}
return 1st_occurence_using_binarySearch(arr, low, high, 1);
}

Given a sorted array, find the element in the array which has minimum absolute difference with the given number.

Eg arr[] = {1, 3, 5, 18, 19, 25} & key=23 → then output is 25

int findMinDiff(int arr[], int n , int key)
{
   int low=0, high=n-1;
   while(low<=high)
   {
       int mid=(low+high)/2;
       if(arr[mid]==key) return arr[mid];
       if(arr[mid]<key) low=mid+1;
       else if(arr[mid]>key) high=mid-1;
   }
   return min(arr[low],arr[high]);
}

Peak Element using binary search (wow)

Here

Find maximum element in Bitonic Array ( same question as above)

Here

Search An Element in Bitonic Array

(here complete solution)