本文主要是介绍牛客网近日最火的一道二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
声明：题目来源于 牛客网 （https://www.nowcoder.com/）
题目描述
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：73604
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例1
输入
5,4,[1,2,4,4,5]
输出
3
分析
-
注意题目中加粗部分，第一个大于等于查找值的位置，这一点很容易被忽略；
-
注意观察示例，数组
[1,2,4,4,5]中 大于等于4的值应该是4，第一次出现应该是 [1,2,4,4,5]，索引应该是2，但示例输出3，这意味着，最终的所求结果（即位置）应该是从 1 开始计数的。 -
分析输入参数，这里有 3 个输入参数，题目中并未说明其意义，但是在线编辑器中是有注释的，要注意观察。
-
三个输入参数分别是数组长度、目标值、有序数组。
这里有一个疑问？ 很明显，第一个参数 —— 数组长度，是完全没有必要的，不仅没有必要，反而具有极强的不稳定性，应该是正常开发过程中极力避免的，但为什么会如此出题呢？
我这里做出如下猜测：可能是为了减少算法额外的时间开支。毕竟有了长度之后，在线测试模块可以更快的根据参数构建出真正的 java 数组去测试算法的耗时，而不是浪费一部分时间在计算构建数组上。
解题
我这里提供 2 中解法。第一中是我们最常见的正常思路；第二种是无意中在评论区看到某位大神提供的思路，于是自己尝试了一下。
解法 1：
思路：
代码：
import java.util.*;public class Solution {/*** 二分查找* @param n int整型 数组长度* @param v int整型 查找值* @param a int整型一维数组 有序数组* @return int整型*/public int upper_bound_ (int n, int v, int[] a) {// write code hereif(a[0] >= v) return 1;int left = 0;int right = a.length - 1;int mid = (left + right) / 2;while(left < right){mid = (left + right) / 2;if(a[mid] >= v) {if(a[mid - 1] < v)return mid + 1;elseright = mid;}else{left = mid;}}return n + 1;}
}
解法 2：
思路：
代码：
import java.util.*;public class Solution {/*** 二分查找* @param n int整型 数组长度* @param v int整型 查找值* @param a int整型一维数组 有序数组* @return int整型*/public int upper_bound_ (int n, int v, int[] a) {if(a[0] >= v) return 1;// write code hereint left = 0;int right = (0 + (n - 1)) / 2;int max = n - 1;while(left < right){if(a[right] >= v){max = right;if(a[right - 1] < v)return right + 1;right = left + (right - left) / 2;}else{left = right;right = right + (max - right) / 2;}}return n + 1;}
}
这篇关于牛客网近日最火的一道二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
