Binary Search

Best case – O (1) comparisons
Worst case – O (log n) comparisons
Average case – O (log n) comparisons

*** Collections.binarySearch() in Java with Examples.
*** Arrays.binarySearch() in Java with examples
*** How to calculate mid in binary search for larger array. 
int mid =(low + high) / 2;
This fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231 – 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.Use:  int mid = low + ((high – low) / 2);

Few problems where binary search is applicable.

  1. Find frequency of each element in a limited range array in less than O(n) time
    Given an sorted array of positive integers, count number of occurrences for each element in the array. Assume all elements in the array are less than some constant M. Do this without traversing the complete array. i.e. expected time complexity is less than O(n). Code  GFG
    Algo: Since we don’t need to traverse the entire array and the array is sorted it’s like a hint to use binary search. Now We keep spliting the array till, we find array where a[h] = a[l]. when this happens we know the count of element. We keep doing this for the entire array.


  2. *** Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array. GFG.  Code Asked in Amazon. 
    Algo:
    1. Linear
    2.Use binary search. We need to check if mid satisfies the condition that it is greater then it’s adjacent numbers. If yes then it’s the max. Else we need to change the loop-up are. So the deciding factor that we need to check if a[mid] < a[mid+1] (check few example for clarity). We need to handle the case that if the max occurs at i=0.
    Time Complexity: O(Logn)
    *** Similar: Find the point where a monotonically increasing function becomes positive first time. GFG.
    Algo: Since a function is only given we can’t directly apply binary search as we don’t know the end. To apply binary search we need start and end index. So we need to find the range to which we will apply binary search. Since the function is monotonically increasing we will try to get two range in which the function value changes sign. Then we will apply binary search on that range.
    Check the code for range(exponential search). That will be helpful. Rest is binary search, which is simple.
    And as always we have to take care of edge case like, of first and last element and have additional problem specific checks.
    *** Similar Suppose you have a sorted array of infinite numbers, how would you search an element in the array?
    Similar: Find bitonic point in given bitonic sequence You are given a bitonic sequence, the task is to find Bitonic Point in it. A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing. GFG


  3. Find a Fixed Point in a given array – Given an array of n distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. GFG.   Code
    Algo:
    1. We can simply achieve O(n) using linear search
    2. We can do better by using binary search. Base case will be comparing mid index and mid index value. Time Complexity: O(Logn).
    Similar: ** Same with duplicate values. GFG. Code
    Algo: Check GFG.


  4. Given a sorted array and a value x, the floor of x is the largest element in array smaller than or equal to x.  GFS.  Code
    Algo:
    1. the first approach is O(n) time. Linearly traverse the array and ….
    2. O(logn). Yes we can do better then O(n). Do a binary search and find the range in which the given x lies.
    Similar: Given a sorted array 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. Link
    Similar: Ceiling in a sorted array 
    Similar: Given an sorted array of size n. Find number of elements which are less than or equal to given element.  


  5. Given a binary array sorted in non-increasing order, count the number of 1’s in it. GFS   Code
    Algo:
    1. Linear Search. O(n)
    2. Binary Search O(logn). Check the base condition to handle the last element


  6. *** Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn). GFG
    Asked in – Google, Microsoft
    This question has many applications.
    OR
    Find the first and last occurence of a given item.
    Code
    Algo: The idea is to find the first and last occurence of the given item x. We use binary search for that as data is sorted. Need to be careful with the condition for searching for first and last occurence. This is because the numbers are repeated.
    If the numbers are not repeated then it would be a simple case of binary search. But then there are repeated number we need to have proper check when changing low/high. Check the question link below in GFG.
    Similar: 
    Find first and last occurrences of an element in a sorted array GFG
    OR Given a sorted array of integers, find the starting and ending position of a given target value.


  7. Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
    Time Complexity: O(mLogn) where m is number of rows and n is number of columns in matrix.
    Algo: We need to traverse each row and find the first occurence of one. Since the row is sorted we will get the one’s count in the row.  We can stop the program when number of one equals the max number of column. The code is similar to the above question –  Find first and last occurrences of an element in a sorted array GFG 


  8. 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]. GFS
    Algo: 
    Since the element will be present only one position left or right, when we check middle we also check the left and right position as well. Since we have checked both adjacent position of mid, we can skip those in the next loop, so instead of shifting low or high by 1, we shift it by 2.


  9. ** Find k closest elements to a given value. Given a sorted array arr[] and a value X, find the k closest elements to X in arr[]. GFG.
    Algo: As we thought 😛
    We finalize an index(referred as crossover) and then move to the left and right to that index(this index is essential –  the point before which elements are smaller than or equal to x and after which greater than x). At each turn we check which of the element on the left or on right has the minimum difference with the given k and print/save that. Then we update the right/left pointer accordingly. We need to make sure to handle the case when either the right side or left side gets exhausted first.

    Similar:
     Find the element before which all the elements are smaller than it, and after which all are greater. GFG. This is a sub-problem over the above problem. We just need to find the crossover point.


  10. ** Given a sorted array in which all elements appear twice (one after one) and one element appears only once. Find that element in O(log n) complexity.  GFG
    This can be done easily using XOR but that will be O(n) complexity. So we use binary search.
    Algo: All elements before the required have first occurrence at even index (0, 2, ..) and next occurrence at odd index (1, 3, …). And all elements after the required element have first occurrence at odd index and next occurrence at even index.
    1) Find the middle index, say ‘mid’.
    2) If ‘mid’ is even, then compare arr[mid] and arr[mid + 1]. If both are same, then the required element after ‘mid’ else before mid.
    3) If ‘mid’ is odd, then compare arr[mid] and arr[mid – 1]. If both are same, then the required element after ‘mid’ else before mid.


  11. Binary Search for Rational Numbers without using floating point arithmetic. 
    Algo: We perform normal binary search only but  since we don’t need to use floating point arithmetic we will use multiplication. This is the only thing to note in this problem


  12. *** Find three closest elements from given three sorted arrays Given three sorted arrays A[], B[] and C[], find 3 elements i, j and k from A, B and C respectively such that max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) is minimized. Here abs() indicates absolute value. GFG.
    Algo:

    1)   Start with i=0, j=0 and k=0 (Three index variables for A,
                                      B and C respectively)
    
    //  p, q and r are sizes of A[], B[] and C[] respectively.
    2)   Do following while i < p and j < q and k < r
        a) Find min and maximum of A[i], B[j] and C[k]
        b) Compute diff = max(X, Y, Z) - min(A[i], B[j], C[k]).
        c) If new result is less than current result, change 
           it to the new result.
        d) Increment the pointer of the array which contains 
           the minimum.

  13. ** Minimum time required to produce m items. GFG. I would rather form an equation and solve it instead of using binary search.

  14. Make all array elements equal with minimum cost Given an array which contains integer values, we need to make all values of this array equal to some integer value with minimum cost where the cost of changing an array value x to y is abs(x-y). GFG.
    Algo: Sort the array and print the middle element if n is odd else print any one of two middle element. The median is the value we want to reduce all numbers to. Now calculate the cost.


  15. For each element in 1st array count elements less than or equal to it in 2nd array.
    Asked in Amazon. GFG.
    Algo: Sort the second array and perform a binary search on the second array. This is same as above problem.
    Time Complexity: O(mlogn + nlogn), considering arr1[] and arr2[] are of sizes m and n respectively.


  16.  Search, Insert and Delete in a sorted array.  GFG.
    It’s obvious that to search we need to use binary search. For deleting also we need to first find the element that has to be deleted using binary search and then shift the values.
    For insert, we can first do a binary search and then shift. Other option is to start the end and start shifting the element from i to i+1, till we find the element that is smaller than the element to insert. At which point we break and insert the new element.



  17. Search in an array of strings where non-empty strings are sorted Given an array of strings. The array has both empty and non-empty strings. All non-empty strings are in sorted order. Empty strings can be present anywhere between non-empty strings. GFG
    Algo: Like normal binary search, we compare given str with middle string. If middle string is empty, we find the closest non-empty string x (by linearly searching on both sides). Once we find x, we do standard binary search, i.e., we compare given str with x. If str is same as x, we return index of x. if str is greater, we recur for right half, else we recur for left half.
    Check code on GFG.
    Although this approach works better than linear search, the worst-case runtime for this algorithm is O(n).


  18. ** Search element in a sorted matrix  – Given a sorted matrix mat[n][m] and an element ‘x’. Find position of x in the matrix if it is present, else print -1. Matrix is sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= n-1, first element of row ‘i’ is greater than or equal to the last element of row ‘i-1’. The approach should have O(log n + log m) time complexity. GFG
    This problem is not same as GFG.
    Algo: We need to perform binary search on 2D array. We already know that the array is sorted.
    We consider i_high and i_low(represents the row) like high and low. We pick a j_mid also(represents a column). We calculate i_mid. We already have j_mid. Check if a[i_mid][j_mid] is the searched value. If not we need to consider other array element. Remember we are playing with rows here, we finalize the row(n in doing so we are always keeping the j_mid constant). When we reduce it to one row, we perform a binary search on the remaining row.


  19.  [Skip] Find a peak element in a 2D array

  20. Given an array that represents elements of arithmetic progression in order. One element is missing in the progression, find the missing number. CodeCode
    Algo: It’s a arithmetic progression, we use this info to check if we need to check the first/second half of the array. We can calculate the diff =  (a[n-1] – a[0] )/n.
    Since it’s a AP and we know the difference we know the element that should be present at any given index. The formula is = a[0] + (n-1)*diff.
    We use this formula to check if the middle element if greater/less then the expected value at that index.
    Now we check the middle element generally, here we will check mid+1 and mid-1 to see it those are the missing numbers.


  21. [Skip] Given a circle with N defined points and a point M outside the circle, find the point that is closest to M among the set of N. O(LogN). Code

  22. Given an integer array and a positive integer k, count all distinct pairs with difference equal to k. GFG.
    Algo: There are multiple approach to this problem.
    1. Use Hashing
    2. Use Binary Search after sorting –

    1) Initialize count as 0
    2) Sort all numbers in increasing order.
    3) Remove duplicates from array.
    4) Do following for each element arr[i]
       a) Binary Search for arr[i] + k in subarray from i+1 to n-1.
       b) If arr[i] + k found, increment count. 
    5) Return count.

    Time complexity: The first step (sorting) takes O(nLogn) time. The second step runs binary search n times, so the time complexity of second step is also O(nLogn). Therefore, overall time complexity is O(nLogn).3. ***Use Sorting –  Sort the array arr. Take two pointers, l and r, both pointing to 1st element. Take the difference arr[r] – arr[l]. If value diff is K, increment count and move both pointers to next element. if value diff > k, move l to next element. if value diff < k, move r to next element. return count.
    Basically we are moving our pointers such that at any time if we exceed the given difference we adjust our value(like two pointers problem).


  23. Find if a given integer x appears more than n/2 times in a sorted array of n integers.
    Time Complexity: O(Logn) GFG
    Algo: We can use Boyer–Moore majority vote algorithm but that has complexity O(n). Since the data is sorted we can use binary search. We find the first occurence of the element. Th condition below is simple(we don’t need to find x’s last occurence, we can jsut check a[i+n/2]).
    (((i + n/2) <= (n -1)) && arr[i + n/2] == x)


  24. Find missing number in an array of consecutive numbers. Code GFG
    Algo: We can use XOR here  but binary search gives a better time complexity.
    In binary search the condition that we move to search in left/right half is important here. Since the numbers are consecutive and sorted, we can take the mid index and mid element. We we add these it should be equal to high element. If not then there’s a number missing in there.


  25. [Skip] Find number of pairs (x, y) in an array such that x^y > y^x. GFG.
    Algo:  The problem can be solved in O(nLogn + mLogn) time. The trick here is, if y > x then x^y > y^x with some exceptions. Following are simple steps based on this trick.1) Sort array Y[].
    2) For every x in X[], find the index idx of smallest number greater than x (also called ceil of x) in Y[] using binary search or we can use the inbuilt function upper_bound() in algorithm library.
    3) All the numbers after idx satisfy the relation so just add (n-idx) to the count.


  26. ** Find the smallest missing element in a sorted array – Given a sorted array of n distinct integers where each integer is in the range from 0 to m-1 and m > n. Find the smallest number that is missing from the array. GFG.  Algo
    1. Linear -Time Complexity: O(n)
    2. Binary Search for every m in the given array –  Time Complexity: O(m log n)3. **Modified Binary Search – Time Complexity: O(log n)
    …1) If the first element is not same as its index then return first index.
    …2) Else get the middle index say mid
    …………a) If arr[mid] greater than mid then the required element lies in left                                      half.
    …………b) Else the required element lies in right half.


  27. Given a binary array sorted in non-increasing order, count the number of 1’s in it. GFG
    Algo:  The idea is to look for last occurrence of 1 using Binary Search. Once we find the index last occurrence, we return index + 1 as count.
    Time complexity: O(Logn)


  28. *** Given a number n, find the cube root of n GFG Code
    Algo: This can be done using binary search. But we will have to handle floating point numbers here.
    We basically generate the cube for mid and check if that values lies within the permissible error range like here we have considered e(.0000001). So if the generated cube and n have a diff of e (either positive or negative) we should be good.


  29. *** Square Root of Integer. GFG  Code – Amazon, FB, Microsoft
    Algo: This is exactly similar to the above problem. 
    The Binary Search can be further optimized to start with ‘start’ = 0 and ‘end’ = x/2. Simple using binary search. Take int as long or big int to handle big numbers.
    The Binary Search can be further optimized to start with ‘start’ = 0 and ‘end’ = x/2.


  30. Given a sorted array of n elements containing elements in range from 1 to n-1 i.e. one element occurs twice, the task is to find the repeating element in an array. GFG
    Algo: Since the number are sorted and in range we can use the array index and value at index to decide the part of array to search.


  31. Given hypotenuse and area of a right angle triangle, get its base and height and if any triangle with given hypotenuse and area is not possible, print not possible.
    GFG 


     

  32. Given n coordinate (x, y) of points on 2D plane and Q queries. Each query contains an integer r, the task is to count the number of points lying inside or on the circumference of the circle having radius r and centered at the origin. GFG
    Algo:
    The equation for the circle centered at origin (0, 0) with radius r, x2 + y2 = r2. And condition for a point at (x1, y1) to lie inside or on the circumference, x12 + y12 <= r2.
    A Naive approach can be for each query, traverse through all points and check the condition. This take O(n*Q) time complexity.
    An Efficient approach is to precompute x2 + y2 for each point coordinate and store them in an array p[]. Now, sort the array p[]. Then apply binary search on the array to find last index with condition p[i] <= r2 for each query.
    Time Complexity: O(n log n) for preprocessing and O(Q Log n) for Q queries.


  33. *** Given an integer n, write a function that returns count of trailing zeroes in n! GFG
    Algo: We can easily observe that the number of 2s in prime factors is always more than or equal to the number of 5s. So if we count 5s in prime factors, we are done. How to count total number of 5s in prime factors of n!? A simple way is to calculate floor(n/5). For example, 7! has one 5, 10! has two 5s. It is done yet, there is one more thing to consider. Numbers like 25, 125, etc have more than one 5. For example if we consider 28!, we get one extra 5 and number of 0s become 6. Handling this is simple, first divide n by 5 and remove all single 5s, then divide by 25 to remove extra 5s and so on.

    Trailing 0s in n! = Count of 5s in prime factors of n!
                      = floor(n/5) + floor(n/25) + floor(n/125) + ....

    On the same lines:
    Given a number n. The task is to find the smallest number whose factorial contains at least n trailing zeroes. GFG.
    n                       0 – 4 | 5 – 9 | 10 – 14| 15 – 19| 20 – 24
    count of  zero     0  |     1  |    2      |    3       |     4
    So the answer should be 5 * (n-1)


  34. Count digits in a factorial.
    Algo 1: We know, log(a*b) = log(a) + log(b)
    log( n! ) = log(1*2*3……. * n)
    = log(1) + log(2) + …….. +log(n)
    Now, observe that the floor value of log base 10 increased by 1, of any number, gives the number of digits present in that number. Hence, output would be : floor(log(n!)) + 1.
    Algo 2: Kamenetsky’s formula

    It approximates the number of digits in a factorial by :
    f(x) =    log10( ((n/e)^n) * sqrt(2*pi*n))
    
    Thus , we can pretty easily use the property of logarithms to ,
    f(x) = n* log10(( n/ e)) + log10(2*pi*n)/2

    On the same lines:  Given a number n find the smallest number whose factorial contains at least n digits. GFG.
    Algo: We can use the above formula to get the range.


  35. *** Print all possible sums of consecutive numbers with sum N. GFG
    Asked in Microsoft.
    Algo: One important fact is we can not find consecutive numbers above N/2 that adds up to N, because N/2 + (N/2 + 1) would be more than N. So we start from start = 1 till end = N/2 and check for every consecutive sequence whether it adds up to N or not.
    We need to find the sum of consecutive numbers, so we need to keep a sliding window kinda thing – keep track of the start and end window values.


  36.  Given an array that represents elements of geometric progression in order. One element is missing in the progression, find the missing number. It may be assumed that one term is always missing and the missing term is not first or last of series. GFG.
    Algo: The important part here is finding the common ratio of geometric progression.
    ratio = (float) pow(arr[n-1]/arr[0], 1.0/n);
    The use the normal binary search.
  37.  
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s