国外黄冈网站推广软件,下载了网站建设asp,酒店网站html模板,loog图标免费在线设计目录
一、写好二分查找的四个步骤
二、在排序数组中查找元素的第一个和最后一个位置
三、搜索插入位置
四、x的平方根 通过上篇文章【手撕二分查找】#xff0c;我们知道了二分查找的【四要素】#xff1a;初始值、循环条件、mid的计算方式、左右边界更新语句。
循环条件…目录
一、写好二分查找的四个步骤
二、在排序数组中查找元素的第一个和最后一个位置
三、搜索插入位置
四、x的平方根 通过上篇文章【手撕二分查找】我们知道了二分查找的【四要素】初始值、循环条件、mid的计算方式、左右边界更新语句。
循环条件和左右边界更新语句决定了二分查找循环终止时left和right的位置(相错/相等/相邻)
初始值和mid的计算方式要使得中间下标mid覆盖且仅覆盖【搜索空间】中所有可能的下标 一、写好二分查找的四个步骤
1.确定区间形式(【左闭右闭】、【左闭右开】、【左开右开】...)
2.维护区间形式为了维护区间形式要设计初始值、循环条件、左右边界。
满足
·初始值左右边界初始值的区间覆盖整个数组
·循环条件满足区间形式的特点而设。如【左闭右闭】在两者相错时终止循环。所以循环条件为leftright。【左闭右开】在两者相遇时终止循环。所以循环条件为leftright
·左右边界在每次搜索完后需要排除已经搜索过的区间。 3.选择mid的计算方式mid计算方式的选择是为了帮助循环缩小区间避免死循环。
通常都是采取向下调整但是有时候需要向上调整。
如在【左开右闭】中(leftmid、rightmid-1)若采取向下调整mid会在中间两个元素中选择较小的那一个位置当左右指针相邻时mid始终选择较小的最终由于leftmid导致死循环。
解决方法就是保证在左右指针相邻时让mid选择 能够帮助缩小区间的(移动右指针)--向上调整
总结
根据左右边界的更新语句让mid的计算方式 在左右指针相邻时选择能够帮助缩小区间的一个(即:指针不指向mid)。 向上调整mid会选择中间两个元素中较大的(nums[mid]target)---移动右指针【左开右闭】 向下调整mid会选择中间两个元素中较小的(nums[mid]target)---移动左指针【左闭右开】 注意【左闭右闭】、【左开右开】都是向下调整 上述三个步骤以及满足了二分查找的【四要素】但是我们还需要注意返回值
4.返回值通过分析数组中元素的三种情况(都大于、存在、都小于target)以及其对于的返回值判断应该返回什么(最好是画图)
如【左闭右闭】中找出大于等于target的数字下标 考虑nums中元素的三种情况
1.nums中所有元素都小于target时right不更新最终leftnums.length因此当这个关系成立时返回-1
2.nums中存在元素大于等于target时由【循环不变】的关系可知最终应该返回left
3.nums中所有元素都大于target时left不更新left0最终right-1此时应当返回下标0因此返回left 二、在排序数组中查找元素的第一个和最后一个位置
题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
题目描述 给你⼀个按照⾮递减顺序排列的整数数组 nums和⼀个⽬标值 target。请你找出给定⽬标值在数组 中的开始位置和结束位置。 如果数组中不存在⽬标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 ⽰例 1 输⼊nums [5,7,7,8,8,10], target 8 输出[3,4] ⽰例 2 输⼊nums [5,7,7,8,8,10], target 6 输出[-1,-1] ⽰例 3 输⼊nums [], target 0 输出[-1,-1] 提⽰ 0 nums.length 10^5 -10^9 nums[i] 10^9 nums 是⼀个⾮递减数组 -10^9 target 10^9 题目分析
我们需要在非递减数组中找到目标值的开始位置和结束位置。只有当目标值在数组中至少存在一个时才会有开始位置或结束位置。其余情况返回[-1,-1] 我们这里使用两次二分查找分别找开始位置(Search1)和结束位置(Search2)
Search1我们只需要在数组中找到第一个大于等于target的数字下标便可以表示开始位置
Search2可以在数组中找到第一个大于target的数字下标然后令其减1即可表示结束位置
但是在求开始位置时有一种情况无法求出。即当数组中没有target时Search1返回的数字下标是第一个大于target的数字下标
而Search2求的也是第一个大于target的数字下标。因为Search2最终减1导致两指针相错.所以当两指针相错时表示没有target返回[-1,-1] 解题思路
1.确定区间形式我们这里选择【左闭右闭】
2.维护区间形式初始值、循环条件、左右边界
初始值left0rightnums.length-1;
循环条件leftright
左右边界leftmid1rightmid-1
3.选择mid的计算方式向下调整midleft(right-left)/2
4.返回值return leftnums.length?-1:left(Search1)、return left(Search2)--解释如下
注意在这四个步骤中第4步尤其需要注意因为前三步很容易得出但返回值需要考虑数组中元素的三种情况。
对于Search1寻找第一个大于等于target的数字下标 考虑nums中元素的三种情况
当数组中所有元素都小于target时,right不更新最终leftnums.length。但此时应该返回-1
当数组中存在元素大于等于target时按【循环不变】的关系应该返回left
当数组中所有元素都大于等于target时left不更新(0)最终right -1此时应该返回left(0)
当数组中最后一个元素等于target时leftnums.length-1rightleft-1此时返回left 对于Search2寻找的是第一个大于target的数字下标 考虑nums中元素的三种情况
当数组中所有元素都小于等于target时,right不更新最终leftnums.length。但此时应该返回-1
当数组中存在元素大于target时按【循环不变】的关系应该返回left
当数组中所有元素都大于target时left不更新(0)最终right -1此时应该返回left(0)
需要注意的是
当数组最后一个元素(等于target)是结束位置时此时leftnums.length在减1后就表示数组最后一个元素。这里不能因为leftnums.length就返回-1。所以我们的返回语句使用的是return left。这里的最后一个元素包含了数组只有一个元素的情况。
所以我们需要处理当数组中所以元素都小于target时返回 -1的情况 解题代码
class Solution {public static int[] searchRange(int[] nums, int target) {if(nums.length0)return new int[]{-1,-1};int firstsearch1(nums,target);//找到第一个大于等于target的数字下标int endsearch2(nums,target);//找到第一个大于target的数字下标//处理search2中数组最后一个元素小于target的情况if(end1nums[end-1]target)return new int[]{-1,-1};if(firstend-1) return new int[]{first,end-1};else return new int[]{-1,-1};}//找到第一个大于等于target的数字下标private static int search1(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target)leftmid1;//注意这里是 else rightmid-1;}return leftnums.length?-1:left;}//找到第一个大于target的数字下标private static int search2(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target)leftmid1;//注意这里是 else rightmid-1;}return left;}
} 我们这里分别使用两次二分查找一方面是为了让大家可以熟悉二分查找大致流程另一方面可以让大家理解其中的不同之处。
当然还有很多其他题解如我们在数组中找到任意一个target然后再左右移动找到边界即可。 三、搜索插入位置
题目链接35. 搜索插入位置 - 力扣LeetCode
题目描述 给定⼀个排序数组和⼀个⽬标值在数组中找到⽬标值并返回其索引。如果⽬标值不存在于数组中返回它将会被按顺序插⼊的位置。 请必须使⽤时间复杂度为 O(log n) 的算法。 ⽰例 1: 输⼊: nums [1,3,5,6], target 5 输出: 2 ⽰例 2: 输⼊: nums [1,3,5,6], target 2 输出: 1 ⽰例 3: 输⼊: nums [1,3,5,6], target 7 输出: 4 题目分析题目要求返回目标值在数组中的插入位置。其实就是查找第一个大于等于target的数字下标。又因为时间复杂度为O(log n) 我们果断使用二分查找
在上一个题目我们使用了【左闭右闭】的区间形式在本题我们使用【左闭右开】。只是为了让大家熟悉每种区间形式的写法 四步骤
1.确定区间形式【左闭右开】
2.维护区间形式初始值、循环条件、左右边界
初始值left0rightnums.length
循环条件leftright
左右边界leftmid1rightmid
3.选择mid的计算方式向下调整midleft(right-left)/2
4.返回值return left(如下) 考虑nums中元素的三种情况
1.nums中所有元素都小于target时right不更新最终leftrightnums.length因此当这个关系成立时返回left/right
2.nums中存在元素大于等于target时由【循环不变】的关系可知最终可以返回left/right(相遇)
3.nums中所有元素都大于等于target时left不更新left0最终rightleft0此时应当返回下标0因此返回right/left 解题代码
public static int searchInsert(int[] nums, int target) {//区间形式【左闭右开】--据此设计初始值循环条件左右边界mid计算方式int left0;int rightnums.length;//初始值while(leftright){//循环条件int midleft(right-left)/2;//向下调整if(nums[mid]target)leftmid1;//边界设计else rightmid;}return left;} 四、x的平方根
题目链接69. x 的平方根 - 力扣LeetCode
题目描述 给你⼀个⾮负整数 x 计算并返回 x 的 算术平⽅根 。 由于返回类型是整数结果只保留 整数部分 ⼩数部分将被 舍去 。 注意不允许使⽤任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 ⽰例 1 输⼊ x 4 输出 2 ⽰例 2 输⼊ x 8 输出 2 解释 8 的算术平⽅根是 2.82842... , 由于返回类型是整数⼩数部分将被舍去。 提示 0 x 2^31 - 1 (2,147,483,647) 题目分析只需要在一段区间(可以是[0,根号x])内找到一个数t满足 t*tx(t1)*(t1)x
其实也就是在区间内找到第一个数 t使其的平方 小于等于x即可
这个区间内的数是有序的直接使用二分查找 解法1(左闭右开)
1.确定区间形式【左闭右开】
2.维护区间形式初始值、循环条件、左右边界
初始值left0rightx/21;//由于根号xx/2(当x不等于0或1时)并且因为右侧边界为开所以我们这里右侧边界设为x/21
这里将右侧边界设为x/21还有一个好处不需要额外处理x0或x1的情况
注意我们只需要保证初始值的范围覆盖了整个【搜索空间】即可。在这里满足right*rightx
循环条件leftright
左右边界leftmid1rightmid
3.选择mid的计算方式向下调整midleft(right-left)/2
4.返回值return left;//但本题需要额外处理
额外处理
我们知道当leftright时循环终止。 在本题中需要注意当left向右侧移动时(mid*midx--leftmid1)若此时left与right相遇循环终止mid无法更新。我们判断了(mid*midx)但是返回的leftmid1我们还需要额外判断新的mid(在循环外侧再计算一次mid)处的平方是否大于x如果大于x返回的应该是left-1
注意由于本题0 x 2^31 - 1 (2,147,483,647)mid*mid可能会超出int类型需要转换为long类型
解题代码
class Solution {public static int mySqrt(int x) {//左闭右开//if(x0||x1)return x;int left0;int rightx/21;//这里处理了x0或x1的情况int mid0;while(leftright){midleft(right-left)/2;//这里不再是下标而是中间值if((long)mid*midx)leftmid1;else rightmid;}midleft(right-left)/2;if((long)mid*midx)return left-1;return left;}
} 解法2(左开右开)
使用【左开右开】的区间形式解决本题有一个好处因为左右边界都移动到mid处当mid*midx时leftmid否则rightmid。当left1right时循环终止left*leftxright*rightx
这时可以直接返回left不需要额外判断 新的mid处的平方是否大于x。
四步骤
1.确定区间形式【左开右开】
2.维护区间形式初始值、循环条件、左右边界
初始值left0rightx/22//注意我们这里设置rightx/22因为当x等于0或者1时我们让(leftright)02)这样仍然能进入循环(left1right)得出最终结果。而这里left设置为-1或0都可以。只需要保证当特殊情况x0/x1时仍然能进入循环即可
循环条件left1right
左右边界leftmidrightmid
3.选择mid的计算方式向下调整midleft(right-left)/2
4.返回值return left
解题代码
class Solution {public static int mySqrt(int x) {//左开右开int left0;//-1也可以int rightx/22;//重点while(left1right){int midleft(right-left)/2;//这里不再是下标而是中间值if((long)mid*midx)leftmid;else rightmid;}return left;}
}
