二分查找
二分查找要求数组按关键字有序排列，并设置两个指针left和right分别指向数组的开头和末尾，每次查找left和right的中间项mid。
设数组非递减排列：
- 若目标值target等于中间项[mid]，则找到元素；
- 若目标值target小于中间项[mid]，则前往当前范围的左半部分查找，将right置为mid-1；
- 若目标值target大于中间项[mid]，则前往当前范围的右半部分查找，将left置为mid+1；
- 若指针left跑到了right的右边，代表数组已查询完毕，且数组中没有目标值。由此可得循环的结束条件为left>right。
基于Python的二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
代码
def search(nums,target) :
left, right = 0, len(nums) - 1
while left <= right:
pivot = left + (right - left) // 2
if nums[pivot] == target:
return pivot
if target < nums[pivot]:
right = pivot - 1
else:
left = pivot + 1
return -1
|