代码随想录算法训练营第一天|704. 二分查找、27. 移除元素

2023-12-28 02:44
文章标签 算法 随想录 代码 元素 二分 查找 训练营 第一天 27 移除 704

本文主要是介绍代码随想录算法训练营第一天|704. 二分查找、27. 移除元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode.704 二分查找

题目链接:704. 二分查找 - 力扣（LeetCode）

视频链接:二分查找法

相关练习:35. 搜索插入位置 - 力扣（LeetCode）

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

69. x 的平方根 - 力扣（LeetCode）

367. 有效的完全平方数 - 力扣（LeetCode）

思路: 首先看到这个题目,会重点关注的是有序整型数组和所有元素是不重复的字眼。那我们就很容易想到寻找一个数的基本二分查找,了解过的都知道逻辑很简单,就是有点细节把控不好.以至于出错。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？上面的问题就是区间定义没有分清楚，写二分法一般就是左闭右闭[left,right]和左闭右开[left,right)两种，接下来和大家一起讨论，用这两种方法如何解题。

整数二分法

指定的数字(binary_search)

第一种:左闭右闭[left,right]

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=left+((right-left)>>1);//避免溢出if(nums[mid]==target) return mid;//找到target，返回midelse if(nums[mid]>target) right=mid-1;//往左区间[left,mid-1]查找else   left=mid+1; //往右区间[mid+1,right]查找}return -1;//查找失败返回-1}
};

时间复杂度:O(logn)

空间复杂度:O(1)

为了更好理解上面的代码,举个例子简单理解一下:

现在我们需要从序列A={1,5,6,8,9,11,15,16,20}中查找数字11的位置,其中序列是0下标是0到8(下标1到9也是没问题的大家下去可以模拟一下)

1.[left,right]=[0,8],因此下标中点是mid=(left+right)/2=4;A[mid]=A[4]=9;9<11;说明需要在    [mid+1,right]范围内继续找,因此left=mid+1=5;

2.[left,right]=[5,8],因此下标中点是mid=(left+right)/2=6;A[mid]=A[6]=15;15>11;说明需要在[left,mid-1]范围内继续查找,因此right=mid-1=5;

3.[left,right]=[5,5],因此下标中点mid=(left+right)/2=5;A[mid]=A[5]=11;11=11;说明找到了需要查找的数X，返回下标5

1.为什么while循环的条件中是<=，而不是<?

 答:因为初始化right的赋值是nums.length-1,即最后一个元素的索引,而不是nums.length.这两者可能出现在不同功能的二分查找中,区别是;前者是相当于两端都闭区间[left,right],后者相当于左闭右开区间[left,right)。因为索引大小nums.length是越界的，所以我们把right这一边视为开区间。我们这个算法使用的是前者[left,right]两端都闭区间。这个区间其实就是每次进行搜索的区间。while(left<=right)的终止条件是left=right+1;while(left<right)的终止条件是left=right;

2.为什么left=mid+1,right=mid-1?为什么有的代码写的是right=mid或left=mid?

答:刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，当然是去搜索区间 [left, mid-1] 或者区间 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

第二种:左闭右开[left,right)

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size();while(left<right)//因为left == right的时候，在[left, right)是无效的空间，所以使用 <{ int mid=left+((right-left)>>1);if(nums[mid]>target){right=mid;//target 在左区间，在[left, middle)中}else if(nums[mid]<target){left=mid+1;// target 在右区间，在[middle + 1, right)中}else{return mid;   // 数组中找到目标值，直接返回下标}}return -1;}
};

时间复杂度:O(logn);

空间复杂度:O(1)

当然，二分查找也可以使用递归形式:

//二分区间为左闭右闭的[left,right],传入的初值为[0,n-1]
int binarySearch(int* a, int left, int right, int key)
{while (left < right){int mid = left + ((right - left) >> 1);int number = a[mid];if (number < key){return binarySearch(a, mid + 1, right, key);}else if (number > key){return binarySearch(a, left, mid - 1, key);}elsereturn mid;}
}

第一个大于等于X的位置(lower_bound/upper_bound)

例如对下标0开始，有5个元素的序列为{1,3,3,3,6}来说,如果要查询3，则应当得到L=1，R=4;如果要查询5，则应当得到L=R=4;如果要查询6.应该得到L=4,R=5;而查询如果是8，则应该得到L=R=5.显然如果序列中没有X，那么L和R也可以理解为假设序列中存在X，则X应当在的位置.

做法其实和前面的很类似,下面我们来分析一下,假设当前的二分区间为左闭右闭区间[left,right]，那么可以根据mid位置处的元素与欲查询元素x的大小来判断应当往哪个区间查找:

1.如果A[mid]>=x,说明第一个大于等于x的位置一定在mid处或者在mid的左侧，应该往左子区间[left,mid]继续查找,即令right=mid;

 2.如果A[mid]<x,说明第一个大于等于x的元素的位置一定在mid的右侧，应往右区间[mid+1,right]继续查找,即令left=mid+1; 

代码:

//A[]为递增，x为查询数字;
//二分上下界为左闭右闭的[left,right],传入的初值为[0,n]
int low_bound(int A[],int left,int right,int x)
{int mid;while(left<right){mid=(left+right)/2;if(A[mid]>=x)  right=mid;//中间的数大于等于x，往左边区间找[left,mid]else           left=mid+1;//中间的数小于x，往右边区间找[mid+1,right]}return left;
}

注意:1.循环条件为什么是left<right不是left<=right？这是由问题本身决定的.在上面题目中，需要当元素不存在返回-1,这样当left>right是[left,right]就不再是闭区间，可以作为元素不存在的判定原则，因此left<=right满足时循环应当一直执行。但是如果要是区间返回第一个大于等于x的元素，就不需要判断元素本身是不是存在,因为他就算不存在返回的也是"假设他存在，他应该的位置",于是当left==right时， 刚好能夹出唯一的位置，就是需要的结果.

2.由于left==right时while停止,因此最后返回left,right都可以.

3.二分的初始区间应该能覆盖到所有可能返回的结果.下界为0肯定的，那上界为什么是n，不是n-1,考虑到欲查询元素有可能比序列中任何数字都要大，此时应该返回n（即假设它存在，它应该在的位置).故初始化区间为[0,n];当然也有的题目要求不在则返回-1,这时候就不需要取到n,具体问题具体分析.

拓展: 其实这就是C++中lower_bound()函数的用法,返回第一个大于等于x数的位置,不存在则返回最后一个数的下一个位置;对应的也有个upper_bound()函数的用法，它是返回第一个大于x数的位置;这个大家可以去实现下，其实就是A[mid]>=x换成A[mid]>x就可以了.这两个函数大家可以去了解下,具体实现上面其实已经介绍了.

不大于X的最后一个位置 

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

简述下题意就是:就是查询一个数的起始位置和终止位置，不存在这个数就返回-1，所以这里取值范围不需要向上面一样取到n(这里不需要输出最后一个数的下一个位置)；

需要写两个二分，一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数。查找不小于x的第一个位置，较为简单(上面已经讲过了):直接放代码

int l = 0, r = n - 1;
while (l < r) {int mid = l + r >> 1;if (a[mid] < x)  l = mid + 1;else    r = mid;
}

查找不大于x的最后一个位置，便不容易了：

int l1 = l, r1 = n;
while (l1 + 1 < r1) {int mid = l1 + r1 >> 1;if (a[mid] <= x)  l1 = mid;else    r1 = mid;
}

为什么不令r = mid - 1呢？因为如果按照上一个二分的写法，循环判断条件还是l < r,当只有两个元素比如2 2时，l指向第一个元素，r指向第二个元素，mid指向第一个元素，a[mid] <= x，l = mid还是指向第一个元素，指针不移动了，陷入死循环了，此刻l + 1 == r，未能退出循环。
那么直接把循环判断条件改成l + 1 < r呢？此时一旦只有两个元素，l和r差1，循环便不再执行，查找错误。
所以这里出现了二分的典型错误，l == r作为循环终止条件，会出现死循环，l + 1 == r作为循环终止条件，会出现查找错误 

问题如何解决，一种方法就是将查找的区间设置为左闭右开，比如待查找元素在[0,n - 1]范围内，可以写成[0,n)，令r = n，这时候只有两个元素时，r是取最右边元素的后一个位置的，l和r相差2，还会执行循环。
现在再来理解上一段的r1 = mid，说明a[mid] > x时，r = mid就表示待查找元素会是在r的左边，因为r是开区间。上面这种写法修改了循环条件使得二分不会死循环，修改了区间的开闭性使得不会查找错误。另一种解决办法就是：

int l = 0, r = n - 1;
while (l < r){int mid = l + r + 1 >> 1;if (a[mid] <= x) l = mid;else r = mid - 1;}

 整数二分模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

浮点数二分法

首先介绍如何计算根号2的近似值。

对于f(x)=x^2来说,在x属于[1,2]范围内,f(x)是随着x的增大而增大的，这就给使用二分法创造了条件,即可以用如下策略来逼近根号二的值。(这里不妨以精确到10^-5为例)

令浮点数left和right的初值分别是1和2，然后根据left和right的中点mid处f(x)的值与2的大小来选择子区间进行逼近.

如果f(mid)>2,说明mid>根号2,应当在[left，mid]的范围内继续逼近,故令right=mid;

 

 如果f(mid)<2,说明mid<根号2,应该在[mid,right]的范围内继续逼近,故令left=mid. 

代码:

const double eps=1e-5;
double f(double x)
{return x*x;
}
double calsqrt()
{  double left=1,right=2,mid;while(right-left>eps){ mid=(left+right)/2;if(f(mid)>2)  right=mid;else         left=mid;}return mid;}

浮点数二分法模板 

bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l;
}

 LeetCode.27 移除元素

题目链接:27. 移除元素 - 力扣（LeetCode）

视频链接:数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

相关练习:26. 删除有序数组中的重复项 - 力扣（LeetCode）

283. 移动零 - 力扣（LeetCode）

844. 比较含退格的字符串 - 力扣（LeetCode）

977. 有序数组的平方 - 力扣（LeetCode）

思路: 题目要求我们把nums中所有值为val的元素原地删除，需要使用快慢指针技巧:如果fast遇到值为val的元素，则直接跳过，否则就赋值给slow指针，并让slow前进一步。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int fast = 0, slow = 0;while (fast < nums.size()) {if (nums[fast] != val) {nums[slow] = nums[fast];slow++;}fast++;}return slow;}
};

总结

由于好久没有碰编程，这两题加上总结大概花费了3h左右，好在于学到了东西，让我对二分查找有了更好的认识，对开区间和闭区间，对是否需要加上等于号有了更清晰地定义和区分，第二题刚开始并没有想到快慢指针，而是用双层for循环,这样做在力扣上也是可以做的，为了提高算法效率，学习到了快慢指针并连同看了左右指针，有些细节已经忘了，重温了一遍，效果自我感觉不错，明天继续加油!!!

这篇关于代码随想录算法训练营第一天|704. 二分查找、27. 移除元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/544906。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2241（二分+合并数组）

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（简单二分）

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
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2