4

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:

  1. the key is smaller than all items, return 0.
  2. the key is bigger than all items, return items.length.
  3. the key is found at index x, return x+1.
  4. 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.

4

3 回答 3

7

以下是一些符合 OP 搜索要求的 C 代码：

  • 值 < 第一项：返回 0
  • 值包含在数组中：返回找到的索引+1
  • 值不在数组中但<第一项和<最后一项：返回下一个最大值的索引
  • 值 >= 最后一项：返回数组大小

它还演示了 4 种不同类型的二进制搜索：

  • 标准二分搜索
  • 小于等于二分搜索
  • LessThanEqual 或 Last Binary Search
  • 下一个最大的二分搜索

（假设没有重复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;
}

输出：

[-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
  • 该1st列是标准的二分查找
  • 该2nd列是小于二分搜索
  • 该3rd列是小于或最后二进制搜索
  • 该4th列是下一个最大的二进制搜索
于 2015-02-03T21:59:04.567 回答
3
  1. 项目清单

这是一个代码：

  • 如果元素存在，则返回要搜索的元素的 索引
  • 如果数组中不存在搜索的元素，则返回下一个更大元素的索引
  • 如果搜索到的元素大于数组的最大元素，则返回 -1
      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);
    }
  }
于 2016-06-29T06:24:00.240 回答
0

这就是你想要的。它返回下一个更大的元素。

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 ); 
    }
}
于 2013-04-25T16:33:43.793 回答