【算法学习+力扣刷题】二分查找入门题

参考文件：算法--二分查找（python实现） - 百度文库 (baidu.com)

里面讲得很详细，这次用的是python的写法，python本身不支持直接整型相加除以2

完整代码：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        self.nums = nums
        self.target = target

        n_len = len(nums)
        low = 0
        high = n_len - 1
        
        while (low <= high):
            if nums[low] == target:
                return low
            elif nums[high] == target:
                return high
            else:
                mid = low + (high-low) //2  #防止整型溢出，其实python本身应该就可以避免吧？
                if nums[mid] == target:
                    return mid
                # 因为已经判断过了num[mid]不等于target，那么应该从mid左右两边找，应该加减1
                # 而且还有上面边界值的判断相等，取左右端点值更保险了
                elif nums[mid] > target:
                    high = mid - 1
                elif nums[mid] < target:
                    low = mid + 1
        if low>=high:
            return -1

使用的测试用例：

nums=[-1,0,3,5,9,12]      target=2   这个用例很好用

几个需要注意的细节（复盘）：

1.判断条件是low<=high，是为了防止出现区间左右端点相等，从而取不到端点。我认为条件这样设置之后就可以删掉对target是否等于nums[low]和nums[high]的判断。如果要保留的话，条件可以写成while(low

2.mid=low+(high-low)//2是为了防止整型溢出，但是我认为基于python中//2就代表向下取整，直接/2是不能运行的，所以可以写成mid=(low+high)//2，因为在循环里运行的条件就是low<=high，而且low, high均大于等于0，所以这样得到的mid也不会是小于0的数.

3.重点是判断nums[mid]!=target之后，左右端点移到mid的一侧，且不包含mid，mid>target，则target在[low,mid-1]范围内，mid

4.最后跳出循环，说明target不在nums中，可以直接返回return -1，但是加上if low>high更严谨吧，更好读.

以上个人观点仅供参考，新手上路不确定自己的想法判断对不对，欢迎评论留言讨论。这个代码就是最保险的版本了。