↓Skip to main content

二分查找技巧

·1718 words·9 mins
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

六款二分模版
#

1、整数上的二分搜索
#

模板一
#

最经典的二分查找模板，教科书指定二分查找模板。

区分语法

  • 初始条件：left = 0, right = n - 1
  • 循环条件：left <= right
  • 向左查找：right = mid-1
  • 向右查找：left = mid+1
  • mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左加右减，相错终止。

使用说明

  • 二分查找的最基础和最基本的形式。
  • 适合查找在所有元素均不相同的数组中查找某特定元素。

代码实现

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while(left <= right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) { 
            return mid; 
        } else if (nums[mid] < target) {
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    return -1;
}

查找等于 target 的第一个元素下标，即查找 target 左边界。

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while(left <= right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    if (left != nums.length && nums[left] == target) return left;
    return -1;
}

查找等于 target 的最后一个元素下标，即查找 target 右边界。

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while(left <= right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    if (right != -1 && nums[right] == target) return right;
    return -1;
}

模板二
#

Python中bisect源码实现模板，右边界可对应C++中end迭代器。

左闭右开的区间分割方式在数学和计算机中都极为普遍。

区分语法

  • 初始条件：left = 0, right = n
  • 循环条件：left < right
  • 向左查找：right = mid
  • 向右查找：left = mid+1
  • mid指针计算：左右指针和折半向下取整

模板口诀

左闭右开，向下取整，左加右定，相等终止。

使用说明

  • 二分查找的高级方法。
  • 查找条件需要访问元素的直接右邻居。
  • 需要进行后处理。

代码实现

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length;
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) { 
            return mid; 
        } else if (nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.length && nums[left] == target) return left;
    return -1;
}

查找等于 target 的第一个元素下标，即查找 target 左边界。

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length;
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.length && nums[left] == target) return left;
    return -1;
}

查找等于 target 的最后一个元素下标，即查找 target 右边界。

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length;
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) { 
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.length && nums[left] == target) return left;
    if(left > 0 && nums[left - 1] == target) return left - 1;
    return -1;
}

模板三
#

用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

区分语法

  • 初始条件：left = 0, right = n - 1
  • 循环条件：left + 1 < right
  • 向左查找：right = mid
  • 向右查找：left = mid
  • mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左定右定，相邻终止。

使用说明

  • 二分查找的的高级方法。
  • 用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
  • 需要进行后处理。

代码实现

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

查找等于 target 的第一个元素下标，即查找 target 左边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

查找等于 target 的最后一个元素下标，即查找 target 右边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 <= right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[right] == target) return right;
    if(nums[left] == target) return left;
    return -1;
}

模板四
#

ACM/ICPC大佬推荐查询目标元素左边界模板。

区分语法

  • 初始条件：left = 0, right = n - 1
  • 循环条件：left < right
  • 向左查找：right = mid
  • 向右查找：left = mid + 1
  • mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左加右定，相等终止。

使用说明

  • 二分查找的的高级方法。
  • 需要进行后处理。
  • 注：在处理上下边界问题时，一般用模板四模板计算左边界。

代码实现

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

查找等于 target 的第一个元素下标，即查找 target 左边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

查找等于 target 的最后一个元素下标，即查找 target 右边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left > 0 && nums[left - 1] == target) return left - 1;
    return -1;
}

模板五
#

ACM/ICPC大佬推荐查询目标元素右边界模板。

区分语法

  • 初始条件：left = 0, right = n - 1
  • 循环条件：left < right
  • 向左查找：right = mid - 1
  • 向右查找：left = mid
  • mid指针计算：左右指针和折半向上取整

模板口诀

左闭右闭，向上取整，左定右减，相等终止。

使用说明

  • 二分查找的的高级方法。
  • 需要进行后处理。
  • 注：在处理上下边界问题时，一般用模板五模板计算右边界。

代码实现

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left + 1 < nums.length && nums[left + 1] == target) return left + 1;
    return -1;
}

查找等于 target 的第一个元素下标，即查找 target 左边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left + 1 < nums.length && nums[left + 1] == target) return left + 1;
    return -1;
}

查找等于 target 的最后一个元素下标，即查找 target 右边界。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

2、实数上的二分搜索
#

实数上的二分搜索不可以直接比较大小，可以采用 $r-l>eps$ 作为循环条件，$eps$ 为一个较小的数，如 $1e-7$ 等。为避免丢失可能解，缩小范围时 $r=mid$ 或 $l=mid$ ，循环结束时返回最后一个可行解。

l=a; r=b; //初始搜索范围
while(r-l>eps){//判断差值
    double mid=(l+r)/2;
    if(judge(mid))
        l=mid;  //l记录了可行解，循环结束后返回答案l
    else
        r=mid;
}
// l 是答案

还可以运行固定的次数，如运行100次，可达 $10^{-30}$ 精度，一般情况都可以解决问题。

l=a;
r=b;
for(int i=0; i<100; i++) { //运行100次
	double mid=(l+r)/2;
	if(judge(mid))
		l=mid;
	else
		r=mid;
}
// l 是答案

3、二分搜索详解
#

例如，给定n个元素序列，这些元素是有序的（假定为升序），从序列中查找元素x。

用一维数组S[]存储该有序序列，设变量low和high表示查找范围的下界和上界，middle表示查找范围的中间位置，x为特定的查找元素。

3.1 算法步骤
#

（1）初始化。令low=0，即指向有序数组S[]的第一个元素；high=n−1，即指向有序数组S[]的最后一个元素。

（2）判定low≤high是否成立，如果成立，转向第3步，否则，算法结束。

（3）middle=(low+high)/2，即指向查找范围的中间元素。如果数量较大，为避免low+high溢出，可以采用middle=low+(high-low)/2。

（4）判断x与S[middle]的关系。如果x=S[middle]，则搜索成功，算法结束；如果x>S[middle]，则令low=middle+1；否则令high=middle−1，转向第2步。

3.2 算法实现
#

用 BinarySearch(int n, int s[], int x)函数实现折半查找算法，其中 $n$ 为元素个数，$s[]$ 为有序数组，$x$ 为待查找元素。$low$ 指向数组的第一个元素，$high$ 指向数组的最后一个元素。如果 $low≤high$，$middle=(low+high)/2$，即指向查找范围的中间元素。如果$x=S[middle]$ ，搜索成功，算法结束；如果 $x>S[middle]$，则令 $low=middle+1$ ，去后半部分搜索；否则令 $high=middle−1$ ，去前半部分搜索。

3.2.1 非递归算法
# 

int BinarySearch(int s[],int n,int x) { //二分查找非递归算法
	int low=0,high=n-1;  //low指向数组的第一个元素，high指向数组的最后一个元素
	while(low<=high) {
		int middle=(low+high)/2;  //middle为查找范围的中间值
		if(x==s[middle])  //x等于查找范围的中间值，算法结束
			return middle;
		else if(x>s[middle]) //x大于查找范围的中间元素，则从左半部分查找
			low=middle+1;
		else            //x小于查找范围的中间元素，则从右半部分查找
			high=middle-1;
	}
	return -1;
}

3.2.2 递归算法
#

递归有自调用问题，增加两个参数 low 和 high来标记搜索范围的开始和结束。

int recursionBS(int s[],int x,int low,int high) { //二分查找递归算法
	//low指向搜索区间的第一个元素，high指向搜索区间的最后一个元素
	if(low>high)              //递归结束条件
		return -1;
	int middle=(low+high)/2; //计算middle值(查找范围的中间值)
	if(x==s[middle])        //x等于s[middle]，查找成功，算法结束
		return middle;
	else if(x<s[middle]) //x小于s[middle]，则从前半部分查找
		return recursionBS(s,x,low,middle-1);
	else            //x大于s[middle]，则从后半部分查找
		return recursionBS(s,x,middle+1,high);
}

3.2.3 算法分析
#

时间复杂度

二分查找算法，时间复杂度怎么计算呢？如果用T(n)来表示n个有序元素的二分查找算法的时间复杂度，那么：

  • 当n=1时，需要一次比较，T(n)=O(1)。
  • 当n>1时，待查找元素和中间位置元素比较，需要O(1)时间，如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为 $T(\frac{n}{2})$ 。

二分查找的非递归算法和递归算法查找的方法是一样的，时间复杂度相同，均为 $O(logn)$。

空间复杂度

二分查找的非递归算法中，变量占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为 $O(1)$。

二分查找的递归算法，除了使用一些变量外，递归调用还需要使用栈来实现。在递归算法中，每一次递归调用都需要一个栈空间存储，那么我们只需要看看有多少次调用。假设原问题的规模为n，那么第一次递归就分为两个规模为 $\frac{n}{2}$ 的子问题，这两个子问题并不是每个都执行，只会执行其中之一。因为和中间值比较后，要么去前半部分查找，要么去后半部分查找；然后再把规模为 $\frac{n}{2}$ 的子问题继续划分为两个规模为 $\frac{n}{4}$ 的子问题，选择其一；继续分治下去，最坏的情况会分治到只剩下一个数值，那么算法执行的节点数就是从树根到叶子所经过的节点，每一层执行一个，直到最后一层，如图所示。

递归调用最终的规模为1，即 $\frac{n}{2x}=1$，则 $x=logn$ 。假设阴影部分是搜索经过的路径，一共经过了 $logn$ 个节点，也就是说递归调用了 $logn$ 次。递归算法使用的栈空间为递归树的深度，因此二分查找递归算法的空间复杂度为 $O(logn)$ 。

4、二分搜索需要注意的几个问题
#

  1. 必须满足有序性。
  2. 搜索范围。初始时，需要指定搜索范围，如果不知道具体范围，正数可以采用范围 $[0,inf]$ ，有可能为负数可以采用范围[-inf,inf]，inf为无穷大，通常设定为 $0x3f3f3f3f$。
  3. 二分搜索。一般情况下，$mid=(l+r)/2$ 或 $mid=(l+r)»1$ 。如果l和r特别大，为避免 $l+r$ 溢出，可以采用 $mid=l+(r-l)/2$ 。判断二分搜索结束的条件，以及当判断 $mid$ 可行时到前半部分搜索，还是到后半部分搜索，需要具体问题具体分析。
  4. 答案是什么。特别小心搜索范围减少时，是否丢失在mid点上的答案。