二分查找算法

🚀

问题描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标

---

array = [1,2,3,4,5]
left=0
right=len(array)-1
#这是目标数
target = 4

while left<=right:
    mid = (left+right)//2
    if target < array[mid]:
        right = mid-1
    elif target > array[mid]:
        left = left+1
    else:
        print(f'这个目标数的下标是⭐{mid}⭐')
        break

解析

属于暴力解法，从第一个元素依次试出

在while循环里，首先找到中间值
【//】是返回一个不大于原数（原数不巧很有可能是小数）的一个整数

第一个if，如果这个目标数小于中间值，那么说明右边界需要缩短范围，由于不包含它，所以需要减一

在第二个if中，如果目标值大于中间值，那么说明目标值在中间值的右侧，左边界需要缩短范围，由于不包含原本的界限，所以需要加一

如果都相等了，那么就会走else路线并将最终的mid输出

---

我个人的理解：这样记“是闭就沾一”，我的意思是 左闭 left = middle+1, 右闭 right = middle-1 。“两闭加等于” 如果是两个闭区间 while(left <= right)