二分查找 -- 力扣(LeetCode)第704题

2024-04-08 22:36

本文主要是介绍二分查找 -- 力扣(LeetCode)第704题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

https://leetcode.cn/problems/binary-search/description/

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1    

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

思路

这道题前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。例如到底是 while(left < right) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

下面我用这两种区间的定义分别讲解两种不同的二分写法。

二分法 第一种写法

第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)

区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:

代码如下:(详细注释)(C++)

// 版本一
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间,所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间,所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值,直接返回下标}}// 未找到目标值return -1;}
};
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

二分法第二种写法

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

在数组:1,2,3,4,7,9,10中查找元素2,如图所示:(注意和方法一的区别

代码如下:(详细注释)(C++)

// 版本二
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间,在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间,在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值,直接返回下标}}// 未找到目标值return -1;}
};
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

总结

二分法是非常重要的基础算法,为什么很多同学对于二分法都是一看就会,一写就废

其实主要就是对区间的定义没有理解清楚,在循环中没有始终坚持根据查找区间的定义来做边界处理。

区间的定义就是不变量,那么在循环中坚持根据查找区间的定义来做边界处理,就是循环不变量规则。

本篇根据两种常见的区间定义,给出了两种二分法的写法,每一个边界为什么这么处理,都根据区间的定义做了详细介绍。

相信看完本篇应该对二分法有更深刻的理解了。

注意

在下面的代码中,使用 middle = left + (right - left) / 2 而不是 middle = (left + right) / 2 的主要原因是为了防止整数溢出。

当 left 和 right 都很大且接近 int 类型的最大值时,它们的和可能会超出 int 类型能够表示的范围,从而导致溢出。溢出后的结果再除以2,可能会导致一个不正确的中间索引值。

为了避免这种溢出情况,我们计算 right - left,这个差值一定小于或等于 right,然后再加到 left 上。这样即使 right 很大,right - left 仍然是一个可以安全处理的整数,再与 left 相加,并进行整数除法,就可以得到一个正确的中间索引,而不会导致溢出。

因此,虽然 middle = (left + right) / 2 在很多情况下也能正常工作,但在处理非常大的整数时,使用 middle = left + (right - left) / 2 更为稳妥和安全。这是一种常见的二分查找算法中的优化技巧,用于确保代码在极端情况下也能正确运行。

小提示

对于 middle = left + (right - left) / 2,这个表达式中的操作包括加法、减法和整数除法。在这个特定的表达式中,减法和加法具有相同的优先级,并且都是左结合的,所以它们会按照从左到右的顺序进行。整数除法 / 在这个表达式中的优先级低于加法和减法,所以加法和减法会首先进行。

其他语言版本

Java

(版本一)左闭右闭区间

class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid - 1;}return -1;}
}

(版本二)左闭右开区间

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid;}return -1;}
}

Python

(版本一)左闭右闭区间

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里,[left, right]while left <= right:middle = left + (right - left) // 2if nums[middle] > target:right = middle - 1  # target在左区间,所以[left, middle - 1]elif nums[middle] < target:left = middle + 1  # target在右区间,所以[middle + 1, right]else:return middle  # 数组中找到目标值,直接返回下标return -1  # 未找到目标值

(版本二)左闭右开区间

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums)  # 定义target在左闭右开的区间里,即:[left, right)while left < right:  # 因为left == right的时候,在[left, right)是无效的空间,所以使用 <middle = left + (right - left) // 2if nums[middle] > target:right = middle  # target 在左区间,在[left, middle)中elif nums[middle] < target:left = middle + 1  # target 在右区间,在[middle + 1, right)中else:return middle  # 数组中找到目标值,直接返回下标return -1  # 未找到目标值

C

(版本一)左闭右闭区间

// (版本一) 左闭右闭区间 [left, right]
int search(int* nums, int numsSize, int target){int left = 0;int right = numsSize-1;int middle = 0;//若left小于等于right,说明区间中元素不为0while(left<=right) {//更新查找下标middle的值middle = (left+right)/2;//此时target可能会在[left,middle-1]区间中if(nums[middle] > target) {right = middle-1;} //此时target可能会在[middle+1,right]区间中else if(nums[middle] < target) {left = middle+1;} //当前下标元素等于target值时,返回middleelse if(nums[middle] == target){return middle;}}//若未找到target元素,返回-1return -1;
}

(版本二)左闭右开区间 

// (版本二) 左闭右开区间 [left, right)
int search(int* nums, int numsSize, int target){int length = numsSize;int left = 0;int right = length;	//定义target在左闭右开的区间里,即:[left, right)int middle = 0;while(left < right){  // left == right时,区间[left, right)属于空集,所以用 < 避免该情况int middle = left + (right - left) / 2;if(nums[middle] < target){//target位于(middle , right) 中为保证集合区间的左闭右开性,可等价为[middle + 1,right)left = middle + 1;}else if(nums[middle] > target){//target位于[left, middle)中right = middle ;}else{	// nums[middle] == target ,找到目标值targetreturn middle;}}//未找到目标值,返回-1return -1;
}

这篇关于二分查找 -- 力扣(LeetCode)第704题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886568

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3692 二分图最大独立集

题意: 幼儿园里,有G个女生和B个男生。 他们中间有女生和女生认识,男生男生认识,也有男生和女生认识的。 现在要选出一些人,使得这里面的人都认识,问最多能选多少人。 解析: 反过来建边,将不认识的男生和女生相连,然后求一个二分图的最大独立集就行了。 下图很直观: 点击打开链接 原图: 现图: 、 代码: #pragma comment(

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter