NC105二分查找的Python解法
二分查找
http://www.nowcoder.com/questionTerminal/7bc4a1c7c371425d9faa9d1b511fe193
题目：请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
n int整型 数组长度
v int整型 查找值
a int整型一维数组 有序数组
如果数组a中有任何值是大于 查找值v 的 则返回该值的位置 如果数组a中不存在这个数值的话 则输出数组长度加一：
->草稿：
for i in range(n):
if a[n-1] < v:
return n+1
(因为 n 为len(a)，如果没有比测试值更加大的，则返回数组长度n+1）
依题意，要求使用二分法进行分析：
Begin x x x Middle x x x End
接下来就很简单了：
1. 首先确定Middle的值：
Begin = 0
End = n - 1
while Begin < End:
Middle = (Begin + End)//2
(因为涉及到位置需要进行整除法)
If a[Mid] >= v:
Begin = End
else:(不够大的情况)
Begin = Middle + 1
return left +1 (返回序数，因为题目解释了 输出位置从1开始计算）
输出位置从1开始计算
上完整代码，支持Python 3.9运行环境：
#
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
def upper_bound_(self , n , v , a ):
# write code here
if a[n-1] < v:
return n+1
Begin = 0
End = n-1
while Begin < End:
Middle = (Begin + End)//2
if a[Middle] < v:
#那么就从Mid的下一位开始计关注起
Begin = Middle + 1
else:
End = Middle
return Begin + 1
#输出位置从1开始计算
# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
def upper_bound_(self , n , v , a ):
# write code here
if a[n-1] < v:
return n+1
Begin = 0
End = n-1
while Begin < End:
Middle = (Begin + End)//2
if a[Middle] < v:
#那么就从Mid的下一位开始计关注起
Begin = Middle + 1
else:
End = Middle
return Begin + 1
#输出位置从1开始计算
在线编程答案/牛客题霸 答案（Python版） 文章被收录于专栏
所有在线编程题的详细题解以及答案，Python版。
投递牛客等公司10个岗位 >
查看13道真题和解析