leetcode题目：704 二分法
一、回顾顺序搜索
（一） 无序列表的顺序搜索，时间复杂度O(n)
def search(self, nums: List[int], target: int) -> int:
pos = 0
while pos < len(nums):
if nums[pos] == target:
return pos
pos = pos + 1
return -1（二） 考虑有序列表的顺序搜索，时间复杂度O(n)
注意：与无序列表的顺序搜索相比，这种方法只有在列表中没有target的时候才会提高效率
def search(self, nums: List[int], target: int) -> int:
#有序的顺序搜索
pos = 0
while pos < len(nums):
if nums[pos] == target:
return pos
elif nums[pos] > target:
return -1
pos = pos + 1
return -1二、二分法是什么
充分地利用列表有序的特性。
在顺序搜索时，如果一个元素不是目标元素，就剩下n-1个元素需要进行比较。
但二分搜索从列表中间的元素开始进行比较，而不是按顺序搜索列表。如果这个元素就是目标元素，那就立即停止搜索；如果不是则可以利用列表有序的特性，排除一半的元素。如果目标元素比中间的元素大，就可以直接排列表的左半部分和中间的元素。
时间复杂度的计算O(logn)
如表所示，当拆分足够多次后，会得到只含一个元素的列表，这个列表要么是目标元素，要么不是，但搜索过程已经完成。到这一步，需要比较i次，且使得=1，由此可得i=logn
| 比较次数 | 剩余元素的个数 |
| 1 | |
| 2 | |
| 3 | |
| ... | |
| i |
三、什么时候使用
可以使用二分法的前提条件：【==看到这个条件就可以首先思考二分法适用与否】
1. 有序数组 2. 无重复元素
如果有重复元素的话，返回的下标可能不对
四、如何使用
def search(self, nums: List[int], target: int) -> int:
first = 0
last = len(nums) - 1
while first <= last:
midpoint = (first + last) //2 #注意是整除运算符，得整除midpoint才有意义
if target == nums[midpoint] :
return midpoint
elif target < nums[midpoint]:
last = midpoint-1
elif target > nums[midpoint]:
first = midpoint+1
return -1五、· 重点辨析 · 边界条件的判断
例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
(一) 左闭右闭
何为左闭右闭？其实就是最开始定义last的时候，将last定义为：last = len(nums)-1，这样一来，nums[last]一直可以取到值，因此：
- while (first <= last) 要使用 <= ，因为first == last是有意义的【存在nums[last]】，所以使用 <=
- if (nums[midpoint] > target) last要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
(二) 左闭右开
何为左闭右开？其实就是最开始定义last的时候，将last定义为：last = len(nums)，这样一来，最初的nums[last]没有意义
- while (first < last) ，这里使用 < ,因为first == last在区间[left, right)是没有意义的
- if (nums[midpoint] > target) last更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]