二分查找

一、二分查找的思想

基础描述：二分查找核心思想是“分而治之”。每次将查找范围缩小为原来的一半，快速缩小寻找目标值的区间。

前提条件：数据必须是有序的。

分治策略：每次将待查找区间分为两半，通过比较中间元素与目标值，舍弃不可能存在目标值的另一半，逐步缩小搜索范围。

二、具体步骤

根据数组的不同，有不同的写法，一般有“左闭右闭“、”左闭右开“、”左开右闭“三种写法，左开右闭不太常用这里就不细讲，只讲其他两种写法。

左闭右闭：从数组的索引left到right这两个端点都包含在查找范围内。

左闭右开：right不包含在查找范围内。

左开右闭：left不包含在查找范围内。

1.左闭右开

初始化：定义初始值left和right的边界，left=0，right=nums.size()。

循环缩小范围：

循环的终止条件是left<right。（因为right不包含在查找范围内）
计算中间值mid=(left+right)/2。（每次循环均要计算）
比较nums[mid]和target：
- nums[mid]<target时，表示即使在当前区间中间位置的元素依然比target小，区间应该向右边缩小，left变量应该调整为left=mid+1。（因为mid是被查找过的，这里需要+1）
- nums[mid]>target时，表示当前区间中间的元素大于target，区间许需要向左右边缩小，right变量应该调整为right=mid。（因为是左闭右开，所以right是不会被查到的，这里不需要-1）
- 当前面两个判断均不满足时，也就意味着找到了target的值，直接返回mid下标。
当循环终止后，表示数组中没有target元素，根据要求返回特定的值即可。（如-1）

实现代码：

C++：

int binary_search(vector v, int target)
{
    int left = 0, right = v.size() - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (v[mid] > target) right = mid - 1;
        else if (v[mid] < target)left = mid + 1;
        else return mid;
    }
    return -1;
}

Python：

def binary_search(nums,target):
    left = 0
    right = len(nums)

    while left<right:
        mid = (left+right)//2 

        if nums[mid]>target:right = mid
        elif nums[mid]<target: left =mid+1
        else: return mid
    return -1

2.左闭右闭

初始化：定义初始值left和right的边界，left=0，right=nums.size()-1。

循环缩小范围：

循环的终止条件是left <= right。
计算中间值mid = (left+right)/2。（每次循环均要计算）
比较nums[mid]和target：
- nums[mid]<target时，表示即使在当前区间中间位置的元素依然比target小，区间应该向右边缩小，left变量应该调整为left=mid+1。
- nums[mid]>target时，表示当前区间中间的元素大于target，区间许需要向左右边缩小，right变量应该调整为right=mid-1。
- 当前面两个判断均不满足时，也就意味着找到了target的值，直接返回mid下标。
当循环终止后，表示数组中没有target元素，根据要求返回特定的值即可。

实现代码：

C++:

int Binary_search1(vector v, int target)
{
    int left = 0, right = v.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (v[mid] > target)
            right = mid - 1;
        else if (v[mid] < target)
            left = mid + 1;
        else
            return mid;
    }
    return -1;
}

Python：

def binary_search(nums,target):
    left = 0
    right = len(nums)

    while left<=right:
        mid = (left+right)//2 # 整除
    
        if nums[mid]>target:right = mid-1
        elif nums[mid]<target: left =mid+1
        else: return mid
    return -1