二分查找三种情况

def searchInsert(nums, target):
    ‘‘‘
    用二分查找来查找指定元素，将搜索区间分为三部分[left,mid-1],[mid]和[mid+1,right]
    :param nums:
    :param target:
    :return: 元素存在，返回index - 查找元素索引
            元素不存在，返回插入位置索引
    ‘‘‘
    left, right = 0, len(nums) - 1
    while (left <= right):  # 退出循环条件是left>right
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left


print("++++++++测试searchInsert==========")
nums = [1, 3, 5, 5, 5, 6]
target = 5
index = searchInsert(nums, target)
print(‘index=‘, index)


def SearchIndex(nums, target):
    ‘‘‘
    二分查找另一种实现，将搜索区间划分为两部分[left,mid]和[mid+1,right]，此时mid下取整
    :param nums:
    :param target:
    :return:
    ‘‘‘
    left, right = 0, len(nums) - 1
    while (left < right):  # 退出循环条件是left==right,此时两者相等，对于返回左右边界就不用考虑了
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1


print(‘+++++++++测试SearchIndex()++++++++++‘)
nums = [-1, 0, 3, 5, 9, 12]
target = 2
index = SearchIndex(nums, target)
print(‘index=‘, index)


def searchIndex(nums, target):
    ‘‘‘
    二分查找，将区间分为[left,mid-1]和[mid,right]两部分,此时为了避免出现死循环（Left=mid),mid必须上取整
    :param nums:
    :param target:
    :return:
    ‘‘‘
    left, right = 0, len(nums) - 1
    while (left < right):  # 退出循环条件:left=right,不用考虑返回左右端点
        mid = left + (right - left + 1) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:  # 下一步搜索区间变为
            left = mid
        else:
            right = mid - 1
    return -1


print(‘------------测试searchIndex()-----------‘)
index = searchIndex(nums, target)
print(‘index=‘, index)

++++++++测试searchInsert==========
index= 2
+++++++++测试SearchIndex()++++++++++
index= -1
------------测试searchIndex()-----------
index= -1

Process finished with exit code 0