algorithm - 使用二进制搜索在数组中查找数字的位置

Question

我有一个数字数组，比如 nums[n] 。我必须找到位置 'i' 使得 nums[i] 在所有小于 key 的整数中最大。nums 已排序。我知道我可以使用从 i=0 到 nums[i]>=key 的位置的线性搜索来做到这一点。但我想做得更快，所以有人能告诉算法所需的二进制搜索吗？

示例： nums[]={2,4,14,25} 和 key=15 。因此 i 应该是 2 因为 14 是小于 15 的所有其他整数中的最大整数。

Answer 1

请记住，在正常的二分搜索代码中，所使用的 low 和 high 变量表示数组的索引，因此您很容易知道位置。

首先看看是否 a[0]>=key，因为应该至少比 key 少 1 个元素来搜索它。

然后进行二分查找：取出中间元素，如果该元素>=key，则丢弃它右边的所有元素，包括它。

但是，如果 a[mid]<键，则丢弃它左侧的所有元素（包括它）并取出直到现在找到的元素或该元素的最大值。

代码 ：

    if(a[0]>=key)
    print("Some error message");
    int found=-1;
    int low=0,high=n-1;
    while(low<high)
    {
    int mid=(low+high)/2;
    if(a[mid]>=key)
       high=mid-1;
    else
    {
       low=mid+1;
       found=max(found,a[mid]);
    }

  }

现在你知道在这个循环之后，low 将等于 high 所以 print(low) 或 print(high)

Answer 2

韦恩的方法是正确的，我对代码做了一些修改。我的代码是用 Java 编写的。

当 a <= nums[mid] 时，所有大于或等于 key 的数字都被丢弃，high 分配给 mid-1。所以当循环结束时，high 是第一个小于 key 或 -1 的数字。-1 表示给定数组中没有数字小于键。

public static int lessThan(int[] nums, int key){
    if(nums == null || nums.length == 0) return -1;
    int low = 0, high = nums.length -1;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(key <= nums[mid]){
            high = mid - 1;
        }else {
            low = mid +1;
        }
    }
    return high;
}