Find the first element in a sorted array that is greater than the target

In a general binary search, we are looking for a value which appears in the array. Sometimes, however, we need to find the first element which is either greater or less than a target.

Here is my ugly, incomplete solution:

// Assume all elements are positive, i.e., greater than zero
int bs (int[] a, int t) {
  int s = 0, e = a.length;
  int firstlarge = 1 << 30;
  int firstlargeindex = -1;
  while (s < e) {
    int m = (s + e) / 2;
    if (a[m] > t) {
      // how can I know a[m] is the first larger than
      if(a[m] < firstlarge) {
        firstlarge = a[m];
        firstlargeindex = m;
      }
      e = m - 1; 
    } else if (a[m] < /* something */) {
      // go to the right part
      // how can i know is the first less than  
    }
  }
}

Is there a more elegant solution for this kind of problem?

Solution 1:

One way of thinking about this problem is to think about doing a binary search over a transformed version of the array, where the array has been modified by applying the function

f(x) = 1 if x > target
       0 else

Now, the goal is to find the very first place that this function takes on the value 1. We can do that using a binary search as follows:

int low = 0, high = numElems; // numElems is the size of the array i.e arr.size() 
while (low != high) {
    int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
    if (arr[mid] <= target) {
        /* This index, and everything below it, must not be the first element
         * greater than what we're looking for because this element is no greater
         * than the element.
         */
        low = mid + 1;
    }
    else {
        /* This element is at least as large as the element, so anything after it can't
         * be the first element that's at least as large.
         */
        high = mid;
    }
}
/* Now, low and high both point to the element in question. */

To see that this algorithm is correct, consider each comparison being made. If we find an element that's no greater than the target element, then it and everything below it can't possibly match, so there's no need to search that region. We can recursively search the right half. If we find an element that is larger than the element in question, then anything after it must also be larger, so they can't be the first element that's bigger and so we don't need to search them. The middle element is thus the last possible place it could be.

Note that on each iteration we drop off at least half the remaining elements from consideration. If the top branch executes, then the elements in the range [low, (low + high) / 2] are all discarded, causing us to lose floor((low + high) / 2) - low + 1 >= (low + high) / 2 - low = (high - low) / 2 elements.

If the bottom branch executes, then the elements in the range [(low + high) / 2 + 1, high] are all discarded. This loses us high - floor(low + high) / 2 + 1 >= high - (low + high) / 2 = (high - low) / 2 elements.

Consequently, we'll end up finding the first element greater than the target in O(lg n) iterations of this process.

Here's a trace of the algorithm running on the array 0 0 1 1 1 1.

Initially, we have

0 0 1 1 1 1
L = 0       H = 6

So we compute mid = (0 + 6) / 2 = 3, so we inspect the element at position 3, which has value 1. Since 1 > 0, we set high = mid = 3. We now have

0 0 1
L     H

We compute mid = (0 + 3) / 2 = 1, so we inspect element 1. Since this has value 0 <= 0, we set mid = low + 1 = 2. We're now left with L = 2 and H = 3:

0 0 1
    L H

Now, we compute mid = (2 + 3) / 2 = 2. The element at index 2 is 1, and since 1 ≥ 0, we set H = mid = 2, at which point we stop, and indeed we're looking at the first element greater than 0.

Solution 2:

You can use std::upper_bound if the array is sorted (assuming n is the size of array a[]):

int* p = std::upper_bound( a, a + n, x );
if( p == a + n )
     std::cout << "No element greater";
else
     std::cout << "The first element greater is " << *p
               << " at position " << p - a;

Solution 3:

After many years of teaching algorithms, my approach for solving binary search problems is to set the start and the end on the elements, not outside of the array. This way I can feel what's going on and everything is under control, without feeling magic about the solution.

The key point in solving binary search problems (and many other loop-based solutions) is a set of good invariants. Choosing the right invariant makes problem-solving a cake. It took me many years to grasp the invariant concept although I had learned it first in college many years ago.

Even if you want to solve binary search problems by choosing start or end outside of the array, you can still achieve it with a proper invariant. That being said, my choice is stated above to always set a start on the first element and end on the last element of the array.

So to summarize, so far we have:

int start = 0; 
int end = a.length - 1; 

Now the invariant. The array right now we have is [start, end]. We don't know anything yet about the elements. All of them might be greater than the target, or all might be smaller, or some smaller and some larger. So we can't make any assumptions so far about the elements. Our goal is to find the first element greater than the target. So we choose the invariants like this:

Any element to the right of the end is greater than the target.
Any element to the left of the start is smaller than or equal to the target.

We can easily see that our invariant is correct at the start (ie before going into any loop). All the elements to the left of the start (no elements basically) are smaller than or equal to the target, same reasoning for the end.

With this invariant, when the loop finishes, the first element after the end will be the answer (remember the invariant that the right side of the end are all greater than the target?). So answer = end + 1.

Also, we need to note that when the loop finishes, the start will be one more than the end. ie start = end + 1. So equivalently we can say start is the answer as well (invariant was that anything to the left of the start is smaller than or equal to the target, so start itself is the first element larger than the target).

So everything being said, here is the code.

public static int find(int a[], int target) {
    int st = 0; 
    int end = a.length - 1; 
    while(st <= end) {
        int mid = (st + end) / 2;   // or elegant way of st + (end - st) / 2; 
        if (a[mid] <= target) {
            st = mid + 1; 
        } else { // mid > target
            end = mid - 1; 
        }
    }
    return st; // or return end + 1
}

A few extra notes about this way of solving binary search problems:

This type of solution always shrinks the size of subarrays by at least 1. This is obvious in the code. The new start or end are either +1 or -1 in the mid. I like this approach better than including the mid in both or one side, and then reason later why the algo is correct. This way it's more tangible and more error-free.

The condition for the while loop is st <= end. Not st < end. That means the smallest size that enters the while loop is an array of size 1. And that totally aligns with what we expect. In other ways of solving binary search problems, sometimes the smallest size is an array of size 2 (if st < end), and honestly I find it much easier to always address all array sizes including size 1.

So hope this clarifies the solution for this problem and many other binary search problems. Treat this solution as a way to professionally understand and solve many more binary search problems without ever wobbling whether the algorithm works for edge cases or not.

Solution 4:

How about the following recursive approach:

public static int minElementGreaterThanOrEqualToKey(int A[], int key,
    int imin, int imax) {

    // Return -1 if the maximum value is less than the minimum or if the key
    // is great than the maximum
    if (imax < imin || key > A[imax])
        return -1;

    // Return the first element of the array if that element is greater than
    // or equal to the key.
    if (key < A[imin])
        return imin;

    // When the minimum and maximum values become equal, we have located the element. 
    if (imax == imin)
        return imax;

    else {
        // calculate midpoint to cut set in half, avoiding integer overflow
        int imid = imin + ((imax - imin) / 2);

        // if key is in upper subset, then recursively search in that subset
        if (A[imid] < key)
            return minElementGreaterThanOrEqualToKey(A, key, imid + 1, imax);

        // if key is in lower subset, then recursively search in that subset
        else
            return minElementGreaterThanOrEqualToKey(A, key, imin, imid);
    }
}

Solution 5:

public static int search(int target, int[] arr) {
        if (arr == null || arr.length == 0)
            return -1;
        int lower = 0, higher = arr.length - 1, last = -1;
        while (lower <= higher) {
            int mid = lower + (higher - lower) / 2;
            if (target == arr[mid]) {
                last = mid;
                lower = mid + 1;
            } else if (target < arr[mid]) {
                higher = mid - 1;
            } else {
                lower = mid + 1;
       }
    }
    return (last > -1 && last < arr.length - 1) ? last + 1 : -1;
}

If we find target == arr[mid], then any previous element would be either less than or equal to the target. Hence, the lower boundary is set as lower=mid+1. Also, last is the last index of 'target'. Finally, we return last+1 - taking care of boundary conditions.