思路

在一个有序的数组中找到 这个数(target) 和它的下标

1、首先 我们需要有 一个左右指针 和 一个中间指针

2、定义 左指针为第一个即0 与 右指针为最后一个 len(num) -1

3、开始whil循环比大小 比目标值(target) 大的在右边 小的在左边

4、开始判断 如果 mid比目标值小 就缩小检索范围即：mid----right 代码：(右指针替换为中间值-1)

解释：为什么-1 因为等于的话就说明找到目标值了 所以要-1 (缩小范围)

5、 如果 mid比目标值大 就缩小检索范围即：left----mid 代码：(左指针替换为中间值+1)

6、都没有就说明找到了

代码:

num = [1,2,3,4,5]
target #这个为 要找的值
left = 0#左指针
right = len(num)-1 #长度-1为下标 表示右指针
while left <= right:
    mid = (left + right) // 2
    if num[mid] > target:
        right = mid -1
    elif num[mid] < target:
        left = mid +1
    else:
        print(f"寻找的目标值为{target}，它的下标为{mid}")
        break    

递归版

def binarySearch(arr, target, left, right):
    """
    二分查找递归实现
    
    解题思路：
    1. 在有序数组中，每次取中间元素与目标值比较
    2. 如果相等则返回下标
    3. 如果中间元素大于目标值，则在左半部分继续查找
    4. 如果中间元素小于目标值，则在右半部分继续查找
    5. 重复上述过程直到找到目标值或搜索范围为空
    
    主要变量含义：
    arr: 有序数组
    target: 要查找的目标值
    left: 当前搜索范围的左边界
    right: 当前搜索范围的右边界
    mid: 当前搜索范围的中间位置
    """
    # 递归终止条件：搜索范围无效，说明未找到目标值
    if left > right: 
        return -1
    
    # 计算中间位置
    mid = (left + right) // 2
    
    # 找到目标值，返回下标
    if arr[mid] == target: 
        return mid
    
    # 中间值大于目标值，在左半部分继续查找
    if arr[mid] > target:
        return binarySearch(arr, target, left, mid-1)
    # 中间值小于目标值，在右半部分继续查找
    else:
        return binarySearch(arr, target, mid+1, right)

# 使用示例
list = [1,2,3,4,5]
target = 3
print(f"结果: {binarySearch(list, target, 0, len(list)-1)}")

老登教学版-01

left = 0
right = None
def binary_search(lst,target):
    global right, left
    if right is None:
        right = len(lst) - 1
    if left > right:
        return -1
    mid = left + (right - left) // 2  #这种写法是防止栈溢出 也可以: (left + right) // 2
    if lst[mid] == target:
        return mid
    if lst[mid] == target:
        return mid - 1
        return binary_search(lst,target)
    else:
        left = mid + 1
        return binary_search(lst,target)

老登教学版-02

def binary_search_recursive2(lst, target):

    left = 0
    right = None

    def binary_compute():
        nonlocal left, right

        if right is None:
            right = len(lst) - 1

        if left > right:
            return -1

        mid = left + (right - left) // 2

        if lst[mid] == target:
            return mid

        if lst[mid] > target:
            right = mid - 1
            return binary_compute()
        else:
            left = mid + 1
            return binary_compute()

    return binary_compute