modify binary search to find the next bigger item than the key

Question

I want to modify the famous binary search algorithm to return the index of the next bigger item instead of the key being searched.

So we have 4 cases:

the key is smaller than all items, return 0.
the key is bigger than all items, return items.length.
the key is found at index x, return x+1.
the key isn't found, return the index of the next bigger one.

e.g:

data = { 1, 3, 5, 7, 9, 11 };

search for 0 returns 0.
search for 11 or 12 returns 6.

search for 5 or 6 returns 3.

while (low <= high) {
    mid = (low + high) / 2;
    if (data[mid] < val)
        low = mid + 1;
    else if (data[mid] > val)
        high = mid - 1;
    else {
        break;
    }
}

Currently got it working by examining low and high values. Is there any interesting code to do so!

EDIT !!!

here is how I get it working:

    if (low <= high)
        found = (low + high) / 2 + 1;
    else if (low >= data.length)
        found = data.length ;
    else if (high < 0)
        found = -1;
    else
        found = low;

I am looking for a more elegant way!

EDIT II !!!

this code works if no duplicates. to handle the case of duplicates we need to modify the first if condition:

if (low <= high)
    found = (low + high) / 2 + 1;

to iterate until it finds a bigger element.

You're implementing the algorithm of [`std::upper_bound`](http://en.cppreference.com/w/cpp/algorithm/upper_bound). — Mark Ransom, Apr 25 '13 at 16:27
"search for 4 or 5 returns 3" wrong! Search for 4 should return 2, and for 5 return 3. — ElKamina, Apr 25 '13 at 16:28

Michaelangel007 · Answer 1 · 2015-02-04T06:01:42.287

Here is some C code that meet's the OP's requirements for searching:

value < first item: return 0
value is contained in the array: return index found+1
value is not in the array but < first item and < last item: return next largest value's index
value >= last item: return array size

It also demonstrates 4 different types of binary searching:

Standard Binary Search
LessThanEqual Binary Search
LessThanEqual or Last Binary Search
NextLargest Binary Search

(It assumes there are no duplicates in data)

#include <stdio.h>

int BinarySearch( int key, int data[], const int len )
{
    int low  = 0;
    int high = len-1;

    while( high >= low )
    {
        int mid = low + ((high - low) / 2);

        /**/ if (data[mid] < key) low  = mid + 1;
        else if (data[mid] > key) high = mid - 1;
        else return                      mid    ;
    }
    return -1; // KEY_NOT_FOUND
}

int LessThanEqualBinSearch( int key, int data[], const int len )
{
    int min = 0;
    int max = len-1;
    // var max = data.length - 1; // Javascript, Java conversion

    while( min <= max)
    {
        int mid = min + ((max - min) / 2);

        /**/ if (data[mid] < key)  min  = mid + 1;
        else if (data[mid] > key)  max  = mid - 1;
        else   /*data[mid] = key)*/return mid    ;
    }

    if( max < 0 )
        return 0;  // key < data[0]
    else
    if( min > (len-1))
        return -1; // key >= data[len-1] // KEY_NOT_FOUND
    else
        return (min < max)
            ? min  
            : max + 1;
}

int LessThanEqualOrLastBinSearch( int key, int data[], const int len )
{
    int min = 0;
    int max = len-1;
    // var max = data.length - 1; // Javascript, Java conversion

    while( min <= max)
    {
        int mid = min + ((max - min) / 2);

        /**/ if (data[mid] < key)  min  = mid + 1;
        else if (data[mid] > key)  max  = mid - 1;
        else   /*data[mid] = key)*/return mid    ;
    }

    if( max < 0 )
        return 0;     // key < data[0]
    else
    if( min > (len-1))
        return len-1; // key >= data[len-1]
    else
        return (min < max)
            ? min  
            : max + 1;
}

int NextLargestBinSearch( int key, int data[], const int len )
{
    int low  = 0;
    int high = len-1;

    while( low <= high)
    {
        // To convert to Javascript:
        // var mid = low + ((high - low) / 2) | 0;
        int mid = low + ((high - low) / 2);

        /**/ if (data[mid] < key) low  = mid + 1;
        else if (data[mid] > key) high = mid - 1;
        else return                      mid + 1;
    }

    if( high < 0 )
        return 0;   // key < data[0]
    else
    if( low > (len-1))
        return len; // key >= data[len-1]
    else
        return (low < high)
            ? low  + 1
            : high + 1;
}

int main()
{
    int items[] = { 1, 3, 5, 7, 9, 11 };
    int LENGTH  = sizeof(items) / sizeof(items[0]);

    for( int i = -1; i < 14; ++i )
        printf( "[%2d]: == %2d   <= %2d   <| %d   > %d\n", i
        , BinarySearch                ( i, items, LENGTH )
        , LessThanEqualBinSearch      ( i, items, LENGTH )
        , LessThanEqualOrLastBinSearch( i, items, LENGTH )
        , NextLargestBinSearch        ( i, items, LENGTH )
    );   

    return 0;
}

Output:

[-1]: == -1   <=  0   <| 0   > 0
[ 0]: == -1   <=  0   <| 0   > 0
[ 1]: ==  0   <=  0   <| 0   > 1
[ 2]: == -1   <=  1   <| 1   > 1
[ 3]: ==  1   <=  1   <| 1   > 2
[ 4]: == -1   <=  2   <| 2   > 2
[ 5]: ==  2   <=  2   <| 2   > 3
[ 6]: == -1   <=  3   <| 3   > 3
[ 7]: ==  3   <=  3   <| 3   > 4
[ 8]: == -1   <=  4   <| 4   > 4
[ 9]: ==  4   <=  4   <| 4   > 5
[10]: == -1   <=  5   <| 5   > 5
[11]: ==  5   <=  5   <| 5   > 6
[12]: == -1   <= -1   <| 5   > 6
[13]: == -1   <= -1   <| 5   > 6

The 1st column is the standard binary search
The 2nd column is the Less Than binary search
The 3rd column is the Less Than Or Last binary search
The 4th column is the Next Largest binary search

pankaj · Answer 2 · 2018-12-18T17:38:07.913

List item

here is a code that :

returns index of element to be searched if element is present
returns index of next greater element if searched element is not present in array
returns -1 if an element greater than the largest element of array is searched

      public static int ceilSearch(int arr[], int low, int high, int x) {
    int mid;
    if (x <= arr[low])
      return low;
    if (x > arr[high])
      return -1;

    mid = (low + high) / 2; /* low + (high - low)/2 */

    if (arr[mid] == x)
      return mid;

    else if (arr[mid] < x) {
      if (mid + 1 <= high && x <= arr[mid + 1])
        return mid + 1;
      else
        return ceilSearch(arr, mid + 1, high, x);
    } else {
      if (mid - 1 >= low && x > arr[mid - 1])
        return mid;
      else
        return ceilSearch(arr, low, mid - 1, x);
    }
  }

smttsp · Answer 3 · 2015-02-03T07:23:52.763

0

Here is what you want. It returns the next bigger element.

public int binarySearch(int[] arr, int key) {
    int lo = 0;
    int hi = arr.length - 1;int mid = 0;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if      (key < arr[mid]) hi = mid - 1;
        else if (key > arr[mid]) lo = mid + 1;
        else return mid;
    }
    return -Math.min(lo, hi)-2;
}


public int myBinarySearch(int[] arr, int key){
     int x = binarySearch(arr, key);
     if(x >= arr.length-1 || -x > arr.length){
         //whatever you want to return
         return Integer.MAX_VALUE;
     }
     else if(x >= 0)
          return arr[x+1] ;
     else
          return arr[-x-1];
}
public static void main(String args[]) {
    Triall tr = new Triall();
    int arr[] = { 1, 3, 5, 7, 9, 11 }; 
    for( int i = 0; i < 13; i++ ) { 
        int n = tr.myBinarySearch( arr,i ); 
        System.out.println(i + " " + n ); 
    }
}

edited Feb 03 '15 at 07:23

answered Apr 25 '13 at 16:33

smttsp

4,011
3
33
62

actually I want to implement my version of binary search instead of using Collections.binarySearch() – mmohab Apr 25 '13 at 16:38
@smttsp This only works if there are no repeated items in the array. If you have three items that are the same, and the binary search returns the first or second of these, then your approach will not return the next larger item. After the binary search, you have to scan the array upwards to look for a different value. – sfstewman Apr 25 '13 at 16:53
I see this doesn't work. At least helps you find out something :) – smttsp Apr 25 '13 at 16:58
This code is still broken horribly: int arr[] = { 1, 3, 5, 7, 9, 11 }; for( int i = 0; i < 12; ++i ) { int n = myBinarySearch( arr,i ); System.out.println( n ); } – Michaelangel007 Feb 03 '15 at 06:40
@Michaelangelo, you were right, it is working now. Thanks for showing my mistake – smttsp Feb 03 '15 at 07:24
@smttsp Except that is STILL not answering the OP's question; they want the **index** returned, NOT the value in the array. Search: 0, returns 0 Search: 1, returns 1 Search: 2, returns 1 Search: 3, returns 2 – Michaelangel007 Feb 03 '15 at 21:34

modify binary search to find the next bigger item than the key

3 Answers3

Linked