算法（三）二分查找

本文简单介绍一下二分查找算法。

1. 简介

二分查找最容易出错的地方就是边界的处理，处理不好就会进入死循环（在处理l=mid or l=mid+1还是r=mid or r=mid+1）。

基于此，本文把边界处理条件统一为while l + 1 < r，这样在处理边界的时候统一为l=mid和r=mid。这样的结果就是少处理了一个数据。所以在遍历完成以后，需要再检查一下nums[l]和nums[r]是否满足需求。

2.排序数组中寻找target

l, r = 0, len(nums) -1
while l + 1 < r:
    mid = l + (r - l) //2
    if nums[mid] == target:
        return mid
    elif nums[mid] > target:
        r = mid
    else:
        l = mid
if nums[l] == target:
    return l
if nums[r] == target:
    return r
return -1

3. 寻找左边第一个等于target

l, r = 0, len(nums) -1
while l + 1 < r:
    mid = l + (r - l) //2
    if nums[mid] == target:
        r = mid
    elif nums[mid] > target:
        r = mid
    else:
        l = mid
if nums[l] == target:
    return l
if nums[r] == target:
    return r
return -1

4. 寻找右边边第一个等于target

l, r = 0, len(nums) -1
while l + 1 < r:
    mid = l + (r - l) //2
    if nums[mid] == target:
        l = mid
    elif nums[mid] > target:
        r = mid
    else:
        l = mid
if nums[r] == target:
    return r
if nums[l] == target:
    return l
return -1