二分查找法

引言.

题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 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 的平方根 

367. 有效的完全平方数

704. 二分查找