二分查找

Akari2023-11-072024-01-09

观前提示：以下内容均为天王寺科技所属。~~与本人无任何联系。~~
下集预告：十大排序——选择排序

参考网站：

代码随想录-二分查找
 十大编程算法助程序员走上高手之路 | 菜鸟教程
 704. 二分查找 - 力扣（LeetCode）

简介

在引入二分查找之前，先来想一个问题：在一个有序、无重复数组中 （想一想，为什么要求有序且无重复元素？），给一个目标值，要求定义一个函数返回此目标值在数组中的下标。
可能你脑海中第一印象是，遍历数组，依次比较目标值是否与每一个元素相等，相等就返回下标。

int search( int a[], int length, int target )
{
    for ( int i = 0; i < length - 1; i++ )
    {
        if( target == a[i] )
        {
            return i;
        }
    }
    return -1;
}

这种写法遍历每一个元素，太浪费时间，需要额外的内存，但易理解，那么使用二分不失为一种好方法：
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，

如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(log n) 。

限制：

数组元素必须有序
数组中不能有重复元素，必须保证返回值唯一

详解：

二分搜索也称为二分查找或折半查找，它充分利用了元素间的次序关系，采用分治策略，
可在最坏的情况下用 O(log n)完成搜索任务。它的基本思想是，将 n 个元素分成数量大致相同
的两部分，取 a[n/2]与欲查找的 x 作比较，如果 x==a[n/2]则找到 x，算法终止。如果 x＜a[n/2]，
则我们只要在数组 a 的左半部继续搜索 x（这里假设数组元素呈升序排列）。如果 x＞a[n/2]，
则我们只要在数组 a 的右半部继续搜索 x。
二分搜索过程可以描述为以下递归过程：
若待搜区间为空，返回-1；
否则
mid = (low+high)/2;
若 x 等于 a[mid]，搜索成功，返回 mid；
若 x 小于 a[mid]，在左半区间搜索；
若 x 大于 a[mid]，在右半区间搜索；

写法

1、左闭右闭：

int search( int a[], int length, int target ){  //传入数组首地址、长度、待搜索目标值
	int left = 0;
	int right = length-1;                   //因为左闭右闭，所以数组下标为[0, length - 1]
	
	while( left <= right )
        {     //因为左闭右闭，所以是 <= ，left = right 是允许的
		int middle = left + (right - left) / 2;     //防止middle长度越界
		if( target < a[middle] ){       //目标值在middle左边
			right = middle - 1;     //更新右边界
                }
		else if( target > a[middle] ){
			left = middle + 1;        //更新左边界
		}
		else
			return middle;          //即target=a[middle]，说明查找成功，则返回目标值下标
	}
	return -1;      //未找到目标值，返回 -1
}

2、左闭右开：

int search(int a[], int length, int target)
{
    int left = 0;
    int right = length;         //因为左闭右开，所以数组下标为[0, length)

    while ( left < right )      //因为左闭右开，所以是 < ，而left = right是不允许的
    {
        int middle = left + ( right - left ) / 2;
        if ( target < a[middle] ){
            right = middle;         //更新右边界
        }
        else if ( target > a[middle] ){
            left = middle + 1;      //更新左边界
        }
        else
            return middle;         //说明查找成功，返回下标值
    }
    return -1;       //未找到目标值，返回 -1
}

要注意的问题

为什么分为左闭右闭和左闭右开？

我也不知道，反正就是这么规定的，记住就行了，其实也就是两种情况罢了。
每一种情况必须牢记到底是二分的哪种情况，是[ 左闭右闭 ]，还是[ 左闭右开 )，不然程序你是看不懂的，更不要说写了。

区间的定义

左闭右闭时，为什么left<= right？左闭右开时，为什么left < right？
首先，target 所在的区间即为 left 和 right 之间。把它当成数学的区间看待，那么此区间必须是有意义的。
不论哪种情况，right最大所能取到的值都不能越界、区间都要有意义。
左闭右闭：
left <= right是有意义的，因为[left, right]是一个有效区间，可以取到。
左闭右开以此类推。

边界条件

**左闭右闭时，为什么target <= a[middle]时，right = middle - 1？而左闭右开却不是？**
还是区间是否有效的问题。
target < a[middle] 时，right = middle - 1：因为是闭区间[ ]，右边界是可以取到的；而 < 说明target不在此区间，我们要更新查找的空间，即在此区间的左区间，即 middle - 1。如果是middle，那更新了个寂寞……
target > a[middle] 时，right = middle + 1：由上面分析可知，这次要更新的是右区间了，即middle + 1。
左闭右开
这种情况，是[ )了，右区间是取不到的，更新时就要注意了，动手在纸上画画吧！

好了，你已经学会二分了，快去敲代码试试吧！

C++版本

//左闭右闭
class Solution {
public:
    int search( vector<int>& nums, int target ) {
        int left = 0;
        int right = nums.size();

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

// 左闭右开
class Solution {
public:
    int search( vector<int>& nums, int target ) {
        int left = 0;
        int right = nums.size();

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