引言.
题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
一.确定区间—左闭右闭or左闭右开
坚持循环不变量，保持区间规则一致
二.具体情况分析
1.左闭右闭二分查找
left=0
right=len(nums)-1
while (left <= right):
middle = (left + right) //2
if (nums[middle] > target):
right=middle-1
elif (nums[middle] < target):
left=middle+1
else:
return middle
return -1
2.左闭右开二分查找
left=0
right=len(nums)-1
while (left < right):
middle = (left + right) //2
if (nums[middle] > target):
right=middle
elif (nums[middle] < target):
left=middle+1
else:
return middle
return -1
3.左开右闭二分查找
left=0
right=len(nums)-1
while (left < right):
middle = (left + right) //2
if (nums[middle] > target):
right=middle-1
elif (nums[middle] < target):
left=middle
else:
return middle
return -1
4.左开右开二分查找
left=0
right=len(nums)-1
while (left <= right):
middle = (left + right) //2
if (nums[middle] > target):
right=middle
elif (nums[middle] < target):
left=middle
else:
return middle
return -1
三.总结
不论哪种形式的二分查找，其代码整体结构是相同的;区别在于区间边界的开闭情况
left=0
right=len(nums)-1
while (left <=/< right): # 当边界能取相同值时<=;否则就是<
middle = (left + right) //2
if (nums[middle] > target):
right=middle/middle-1 # 开区间是middle,闭区间是middle-1
elif (nums[middle] < target):
left=middle/middle+1 # 开区间是middle,闭区间是middle+1
else:
return middle
return -1
四.Leetcode题目参考
34. 在排序数组中查找元素的第一个和最后一个位置
35. 搜索插入位置
69. x 的平方根
35. 搜索插入位置
704. 二分查找
