做题地址:https://www.nowcoder.com/practice/7bc4a1c7c371425d9faa9d1b511fe193?tpId=188&tags=&title=&diffculty=0&judgeStatus=0&rp=1
题目描述
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
示例1
输入
5,4,[1,2,4,4,5]
输出
3
# # 二分查找 # @param n int整型 数组长度 # @param v int整型 查找值 # @param a int整型一维数组 有序数组 # @return int整型 # class Solution: def upper_bound_(self , n , v , a ): # write code here #二分查找就是从中间开始找的,指定数字范围的两个边界值相加整除2 #有重复数字的有序数组的二分查找 #输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 #列表内最后一位数小于指定时:a[n-1]<v,则n+1 if(a[n-1]<v): return n+1 lo=0 #列表左边位置,从0开始 right=n#列表右边位置,从n开始 while(lo<right): #当左边位置<右边位置时,循环以下 mid=(right+lo)//2 #中间位置,“/”浮点数除,“//”整 if(a[mid]<v): #当中间位置<指定位置,因为是有序数组,所以正确数值一定不在左边了 lo=mid+1 #左边位置序号=中间位置+1,左边开始缩圈了。 else: #如果是中间位置>=指定位置,那么正确数值就一定在左边,右边缩圈。 right=mid #当循环结束,左边位置=右边位置=中间位置,没法缩了,天命。 return lo+1 #列表里是从0开始,但是位置计数是从1开始,所以lo+1