二分查找的几种情况汇总

        在学习算法和刷leetcode的过程中，二分查找是一种非常常见的算法。功能方面，它将查找的复杂度从o(n)降成了o(lgn)。使得查找效率大大提高。在leetcode中，有诸多关于二分查找的变体。因此，掌握好二分查找是非常有必要的。但是，在实际学习过程中，对于二分可能出现的各种情况，我查阅了很多博客和文章，大家给出的代码不统一，也大多没有给出详细的解释。所以，有一段时间，二分算法的几种情况在我脑中乱糟糟的。今天终于花了一些时间把这些情况理清楚了。所以将这几种情况写在这里，以便复习。

        二分查找的主要情况分成7中情况：

        1. 查找对应target位置（返回对应位置，没找到则返回-1）

        2. 查找第一个大于或等于target的位置（返回对应位置，没找到则返回-1）

        3. 查找第一个大于target的位置（返回对应位置，没找到则返回-1）

        4. 查找最后一个小于等于target的位置（返回对应位置，没找到则返回-1）

        5. 查找最后一个小于target的位置（返回对应位置，没找到则返回-1）

        6. 查找第一个等于target的位置（返回对应位置，没找到则返回-1）

        7. 查找最后一个等于target的位置（返回对应位置，没找到则返回-1）

 

        另外，本文中都是在数组的闭区间内进行查找，而且默认数组已经是增序排列。

        

        1. 查找对应target位置（返回对应位置，没找到则返回-1） 

        对应代码为：

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

         2. 查找第一个大于或等于target的位置（返回对应位置，没找到则返回-1）

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

          3. 查找第一个大于target的位置（返回对应位置，没找到则返回-1）

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

         4. 查找最后一个小于等于target的位置（返回对应位置，没找到则返回-1） 

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

         5. 查找最后一个小于target的位置（返回对应位置，没找到则返回-1）

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

         6. 查找第一个等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if mid[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1
    if low <= len(nums)-1 and nums[low] == target:
        return low
    else:
        return -1

        7. 查找最后一个等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    if high >= 0 and nums[high] == target:
        return high
    else:
        return -1