修改二进制搜索以找到比键更大的项目-Java 学习之路

我想修改着名的binary search算法来返回下一个更大的项目的索引而不是被搜索的密钥 .

所以我们有4个案例：

键小于所有项目，返回0 .
键大于所有项目，返回items.length .
在索引x处找到密钥，返回x 1 .
找不到密钥，返回下一个更大的索引 .

例如：

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

搜索0返回0 .
搜索11或12个返回6 .
搜索5或6返回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;
    }
}

目前通过检查低值和高值来实现它 . 有没有有趣的代码可以这样做！

编辑!!!

这是我如何使它工作：

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;

我正在寻找一种更优雅的方式！

编辑II !!!

如果没有重复，此代码有效 . 要处理重复的情况，我们需要修改第一个if条件：

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

迭代直到找到更大的元素 .

3 回答

以下是满足OP搜索要求的一些C代码：

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

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

标准二进制搜索
LessThanEqual二进制搜索
LessThanEqual或Last Binary Search
NextLargest二进制搜索

（它假设 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 列是Less Than二分法搜索
3rd 列是Less Than Or Last二进制搜索
4th 列是Next Largest二进制搜索

回复于 2024-04-27T21:24:33+08:00

列出项目

这是一个代码：

返回 index 要搜索的元素 if element is present
如果搜索的元素不在数组中，则
返回下一个更大元素的索引
如果搜索大于数组最大元素的元素，则
返回-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);
    }
  }

回复于 2024-04-27T21:24:33+08:00

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

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 ); 
    }
}

回复于 2024-04-27T21:24:33+08:00

修改二进制搜索以找到比键更大的项目

3 回答

相关问题