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

标签 algorithm binary-search

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

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

最佳答案

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

先看是否a[0]>=key,因为至少要比key少1个元素才能找到。

然后进行二分查找:取出中间的元素,如果这个元素是 >=key 则丢弃它右边的所有元素,包括它。

但是,如果 [mid] < key ,然后丢弃它左边的所有元素(包括它),并取出到目前为止找到的元素或这个元素的最大值。

代码:

    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)

关于algorithm - 使用二进制搜索查找数组中数字的位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13277292/

相关文章:

java - 按属性对列表进行排序,但保持相同属性的顺序

algorithm - 使用分而治之是否会提高在数组中查找最大值和最小值的时间复杂度

c - 计算网格上连接组的相邻空点的有效方法

c++ - 我想要一个递归函数来使用二进制搜索检查数组的顺序

c++ - 二进制搜索范围

c - 使用递归在 C 中进行二进制搜索

c++ - 使用递归查找数组中的最大值

java - 循环在网络爬虫项目中效果不佳

ruby - 计算类(class)组合以安排学生

c - 如何用更少的迭代找到最大值