Category Archives: binary search

Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row.

For example consider the following matrix.

0 0 1 1
0 0 0 1
0 1 1 1
0 0 0 0

The maximum number of 1s in any row is three which appear in the third row.

The general approach is to find the number of 1s in each row and update the maximum.


There are two ways to find the number of 1s.
  • One simple approach is to linearly search for first 1 and find the count of 1s. This will take O(n) time in worst case. So the overall time complexity would be O(n2).
  • Another faster method is to search for first 1 using binary search since each row is sorted. This will take only O(log n) time and the overall complexity would be O(n log n).

Even more efficient approach can be as follows.

  • Start with the right most element in the first row, keep counting the number of 1s until we reach zero. 
  • Move to the next row and start checking the elements from previous column
    • If the element is zero, just move on to the next row
    • Otherwise count the ones until we reach zero or the first column
  • Repeat the above step for all the rows. At the end, we get the maximum number 1s.

This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.

    Here is the C++ implementation of the above. I have used the lower_bound() method from the standard library to find the left most occurrence of a 1. Look at my previous post to understand how this method works.

    Finding the maximum element in a bitonic array

    Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?

    For example, the input arrays can look like {1, 3, 5, 4, 2} ,  {11, 17, 25, 36, 24, 6}.

    Basically we need to find the point at which the elements start decreasing. It can be anywhere in the array.

    The obvious linear search for maximum takes O(n) time. But we can utilize the sorted property of two parts of the arrays to solve it in O(log n).

    Here is how the algorithm works.

    • Go to the middle element and check if it is greater than both the left and right elements. If it is, then we found the maximum element. 
      • Eg: {1, 3, 5, 4, 2}
    • If the left element is greater than the middle element, we can ignore the right half and search only in left half. 
      • Eg: {1, 5, 4, 3, 2}
    • If the right element is greater than the middle element, we can ignore the left half and search only in right half.
      • Eg: {1, 5, 7, 9, 3}

    We need to handle the cases where the middle element falls on the boundaries of the array. This happens when the entire array is sorted either in ascending order or descending order. Eg: {1, 2, 3, 4, 5} or {5, 4, 3, 2, 1}

    • If the right part is empty, and the middle element is greater than left element, we can eliminate the left part.
    • Similarly if the left part is empty, and the middle element is greater than right element, we can eliminate the right part.

    Test cases:

    1. {1, 3, 5, 4, 2}
    2. {1, 2, 3, 4, 5}
    3. {5, 4, 3, 2, 1}
    4. {1}
    5. {1, 2, 2, 4, 5, 3}
    6. {10, 20}

     Here is the iterative C++ implementation of the above algorithm.

    Forming the nth binary sequence

    A binary sequence contains 0 and 1 only
     

    S.No  Binary sequence
    ——————–
    1     0
    2     1
    3     00
    4     01
    5     10

    Given a number k, we have to design an algorithm to print kth binary sequence.

    Initial approach (not efficient):
     
    Starting from the sequence 0, this algorithm iterates k times. 


    To get the next sequence, in each iteration we do the following.
     check the last index of 0 in the number

    • If it is found change that to 1 and all the digits after that to 0
    • If it is not found, the next sequence contains all 0 which is one  digit longer than previous

    Efficient approach:

    Observe the following. we can have
    ‘2’ single digit numbers
    ‘4’ two digit numbers
    ‘8’ three digit numbers

    ‘2^i’ i digit numbers

    We can find the number of digits in kth sequence by calculating the power of 2 which is less than k .

    For example if
    k is 5, the smallest power (s) of 2 less thank k is 4. So kth sequence has 2 digits.

    To form the the sequence we need to find the binary representation of 
    k – ( 2^1 + 2^2 + …+2^s)
     

    This SPOJ problem is based on the above algorithm.
     

    Here is the C++ program which implements this.

    Next Round – A problem from Codeforces

    This problem is from Codeforces. If you want to solve this problem on your own, follow this link.

    Here is the simplified problem statement.

    Given a list of scores of contestants in a competition, arranged in decreasing order. We have to calculate the number of people qualified for the next round.
    This is determined as follows, consider the score at a given index, Whoever scored more than this score, qualifies for the next round as long as they have a score of greater than zero.

    For example, let us consider the scores {10, 9, 8, 7, 7, 7, 5, 5} and the index (starts from 1) to take as bench mark is 5. we have a total of 6 candidates who qualify for next round.


    If the scores are {0,0,0,0} and the index is 2, no one qualifies for the next round because none of them have a score greater than zero.
     
    In case of {1, 0, 0, 0} and index 2, we have one candidate qualifying for the next round.

    Let us look at the way of solving this problem. We have to handle two cases here.

    Case 1: score[index] > 0
        In this case, we have to find the right most occurrence of the cutoff, which will give the required answer


    Case 2: score[index[ <= 0
        In this case, we have to find the left most occurrence of zero, and count the remaining elements from the beginning.

    Here is the C++ implementation of the above. Since finding the left most and right most elements in a sorted array can be found using binary search, the time complexity of this solution is O(log n).

    Finding the right most occurence of an element in a sorted array

    Given an array of sorted numbers, we have to find the right most occurrence of a number.

    For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index).

    This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).

    Similar to the above problem, we have to utilize binary search to solve this problem in O( log n ) time. Normal binary search returns any index which matches the given value. So, We have to customize binary search to find the right most instance.

    In this modified approach, we have to check if we have already reached the end of the array or the middle is different from it’s next element. If it’s different, we return; otherwise we continue with right half of the array.

    This function is similar C++ library implementation of upper_bound().

    Here is the implementation in C++ which covers various test cases.

    Finding the integer square root of a number

    How do we implement a function to find the integer square root of a number?

    For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)

    A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.

    for( int i = 1; i <= N/2 ; i++ )
    {
        if( i*i >= N )
            return i;
    }

    But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?

    Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.

    If mid2 > N, we confine our search to the left half; otherwise we search in the right half.

    This implementation takes only O(log N) time.

    Here is the C++ implementation. 



    Finding an element in a circularly sorted array

    Given a circularly sorted array, how to search for an element efficiently?

    For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.


    Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.

    We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.

    Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .

               if( arr[low] <= arr[mid]) //left half is sorted
            {
                //If target lies in first half

                if( s >= arr[low] && s < arr[mid] )
                    high = mid – 1;
                else
                    low = mid + 1; // narrow down to right half
            }
            else // Right half is sorted
            {
                if( s > arr[mid] && s <= arr[high] )
                    low = mid + 1;
                else
                    high = mid – 1;
            }

    Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.

     

    How many times a sorted array is rotated?

    Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations?

    For example the array [4, 5, 1, 2, 3] is (right) rotated twice.

    Before proceeding to find a solution, let’s note some observations.

    To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.

    In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.

    A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?

    Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.

    Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.

    We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.

    Next we check if the middle element is the smallest element by comparing it with the previous and next elements.

    if( array[mid] < array[prev] && array[mid] < array[next] )

    If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.

          //if mid is at 0, consider last element as previous
         int prev = (mid – 1 + len) % len;
       //if mid is the last element, consider next element as the first

         int next = (mid + 1) % len;

    Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.

         if( arr[low] <= arr[mid] )
            return findRotations(arr, mid+1, high);
        else
            return findRotations(arr, low, mid-1);
    Here is the C++ code which implements the above algorithm.

    Even more simplified version of the algorithm is given below. 

    int findRotationCount(const vector<int>& arr)
    {
    int low = 0, high = arr.size() - 1;

    while( arr[low] > arr[high] )
    {
    int mid = low + (high - low)/2;
    if( arr[mid] > arr[high] )
    low = mid + 1;
    else
    high = mid;
    }
    return low;
    }
    int findRotateCount(const vector<int>& arr, int low, int high)
    {
    if( arr[low] > arr[high] )
    {
    int mid = low + (high-low)/2;
    if( arr[mid] > arr[high] )
    return findRotateCount( arr, mid+1, high);
    else
    return findRotateCount( arr, low, mid);
    }
    else
    return low;
    }

    Finding the magic index of the array

    Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.

    For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
    If there no such element in the array we can return -1.

    Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.

    Since the array is sorted, we can modify the binary search to solve this problem more efficiently.

    Using binary search we first visit the middle element of the array. 
    If array[mid] = mid, simply return mid.
    If mid > array[mid], there is no way to find magic index on the left half. Think of an example
    [-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2.   If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.

    In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.

    C++ implementation of the above algorithm is given below.

    Finding a number in a sorted array with the least difference from given number

    Given a sorted array and a value, we have to find the closest value (with least difference).
    For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11.

    This problem is actually a variation of binary search where in we have to find out the closest value found the array. If the given value exists in the array, we have to return that.

    A sorted array and binary search gives a hint that we can solve this problem in O( log n) complexity. Here is how we can modify the binary search algorithm to solve this problem.

    As in binary search algorithm, we try to search for the given number in the middle of the array. If the element is found, we just return it, because we got the least difference i.e 0.

    We also maintain two variables one to store the minimum difference found so far (minDiff), and the other (result) to store the corresponding number. In each iteration, we find the difference between the given value and middle value. If this is lesser than minimum difference, we update the two variables.

    At the end of the search we have the required number in the result variable.

    Below is the Java code which implements the above algorithm.