网站建设技术服务公司,行业门户网站开发,许昌住房和城乡建设局网站,中国企业信息查询网找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a; 优选算法专题 目录
二分查找算法的介绍
704. 二分查找
34. 在排序数组中查找元素的第一个和 最后一个位置
35. 搜索插入位置
69. x的平…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 优选算法专题 目录
二分查找算法的介绍
704. 二分查找
34. 在排序数组中查找元素的第一个和 最后一个位置
35. 搜索插入位置
69. x的平方根
总结 二分查找算法的介绍
想必大家对这个算法应该不算陌生了在C语言阶段就已经学习过了。 其是在暴力枚举的基础上进行优化的。例如在一个有序数组中查找某个元素是否存在。 但是二分查找算法也有缺点就是需要数据有二段性不一定是数组全部有序。
二分查找算法其实也是双指针算法中对撞指针的一种拓展主要是利用了数据的二段性。
下面我们就来进行练习。
704. 二分查找
题目 给定一个 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]之间。 思路这里既可以使用最简单的暴力枚举也可以使用二分查找来解决。
代码实现
暴力枚举
class Solution {public int search(int[] nums, int target) {for (int i 0; i nums.length; i) {if (nums[i] target) {return i;}}return -1;}
} 二分查找
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length-1;while (left right) { // 这里得判断的情况int mid (leftright) / 2; // 这里可能会有溢出的风险if (nums[mid] target) {right mid-1;} else if (nums[mid] target) {left mid1;} else {return mid;}}return -1;}
}
注意由于本题数据量不是很大因此 mid (leftright) / 2; 就不会溢出但是当数据量非常大时两者相加就会导致溢出。有小伙伴可能会有疑惑left 为 0right 在 int 中为什么会导致溢出呢确实这种情况是正常的但是当第二次计算mid 且left 为上一次的mid 值呢这就会溢出了。解决办法为mid left (right - left)/2上面这个题目只是来练练手下面才开始真正的算法题。
34. 在排序数组中查找元素的第一个和 最后一个位置
题目 给你一个按照非递减顺序排列的整数数组 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 105-109 nums[i] 109nums 是一个非递减数组-109 target 109 思路题目说给的数组是非递减的什么意思呢 这里要查找的不是一个元素而是一组连续的数据也就是一段连续的子区间。 这里可能有小伙伴会想到我们前面学习的滑动窗口算法求子序列的问题。 但是这里不应该优先使用这个方法因为滑动窗口算法是同向双指针 而这里我们推测出了数据的特性应该优先使用二分查找。
这里是要查找一组数据的端点下标那么我们就可以直接忽略这组数据的中间直接找端点即可。那么这就从查找一段数据变为了查找两个值。但是新的问题又来了怎么找端点呢相信有聪明的小伙伴已经想到怎么做了。直接暴力枚举去遍历数组就完了。没错这虽然是一个笨办法但是总好过没有办法。
遍历的方式从数组最左端开始遍历找左端点接着从数组最右端开始找右端点即可。
代码实现
class Solution {public int[] searchRange(int[] nums, int target) {int[] ans {-1,-1};if (nums.length 0) { // 排除特殊情况return ans;}// 找左端点int left 0;while (left nums.length nums[left] ! target) { // 防止越界left;}if (left nums.length) { // 数组中没有目标值return ans;} else {ans[0] left;}// 找右端点int right nums.length-1;while (right 0 nums[right] ! target) { // 防止越界right--;}if (right 0) {ans[1] right;}return ans;}
}
虽然这是暴力枚举但是从力扣上面的结果来看还是不错的。 上面的方法可以说是流氓做法了不符合题目的要求用二分查找来解决。
二分查找同样还是去找符合数据的左端点和右端点。
寻找左端点过程 寻找右端点过程精简版 上面处理这么多其实就是在证明三件事
1、根据查找的端点位置从而划分了合法区域和非法区域因为端点位置肯定是在有效区域内的。再根据 left 和 right 的相对位置来判断下一步的走向。
左端点left mid 1 --- 跳出非法区域right mid --- 保留在合法区域。
右端点left mid --- 保留在合法区域right mid -1 --- 跳出非法区域。
2、在查找的过程中中点的选取。根据查找的端点位置和第一点的结论从而决定中点的位置。
左端点right mid 的特性可能会导致最后死循环因此中点尽量要靠左即 mid left (right-left) / 2。
右端点left mid 的特性可能会导致最后死循环因此中点尽量要靠右即 mid left (right-left 1) / 2。
3、 查找左端点和右端点的过程中循环条件只能是 left right绝不能出现等于的情况可能会导致死循环。因为一旦相遇并且结果满足 right 或者 left 不动的情况那么就会死循环。
上面这些细节问题处理完之后代码就比较好写了。
代码实现
class Solution {public int[] searchRange(int[] nums, int target) {int[] ans {-1,-1};if (nums.length 0) { // 排除特殊情况return ans;}// 找左端点int left 0;int right nums.length-1;while (left right) {int mid left (right-left) / 2; // 找靠左的位置if (nums[mid] target) {right mid; // 保证在合法区域内} else {left mid1; // 保证有可能跳出非法区域}}// 走到这里说明left与right相遇了if (nums[left] target) { // 判断是否为左端点ans[0] left; // left 与 right 都是可以的} else { // 说明数组中没有要找的数据return ans;}// 找右端点left 0;right nums.length-1;while (left right) {int mid left (right-left1) / 2; // 找靠右的位置if (nums[mid] target) {left mid; // 保证在合法区域内} else {right mid-1; // 保证有可能跳出非法区域}}// 走到这里说明left与right相遇了if (nums[right] target) { // 判断是否为右端点ans[1] right; // left 与 right 都是可以的}return ans;}
}
还有两个要注意的地方 因此数组中一旦存在我们要查找的数据的话肯定是存在左右端点的。
35. 搜索插入位置
题目 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 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提示: 1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104 思路这里和第一题有点类似但不同的是这一题的数组中可能不存在 target 这个数据。但是方法还是类似的。 当 [targetright] 区间是合法区间时right mid --- 保证 right 在合法区间内left mid1 --- 保证 left 有可能进入合法区间mid left (right - left) / 2 --- 靠左的位置。同理当[lefttarget]为合法区间时也是类似的这里就不过多赘述了。
代码实现
1、当 [left, target] 是合法区间时
class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length-1;// 假设[left, target]是合法区间while (left right) {int mid left (right-left1) / 2;if (nums[mid] target) {right mid-1;} else {left mid;}}// 判断是否存在if (nums[left] target) { // 实际存在return left;} else { // 不存在// 判断是插入左边还是右边位置if (nums[left] target) {return left;} else {return left1;}}}
}
2、 当 [targetright] 是合法区间时
class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length-1;// 假设[target, right]是合法区间while (left right) {int mid left (right-left) / 2;if (nums[mid] target) {right mid;} else {left mid1;}}// 判断是否存在if (nums[left] target) { // 实际存在return left;} else { // 不存在// 判断是插入左边还是右边位置if (nums[left] target) {return left;} else {return left1;}}}
}
69. x的平方根
题目 给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1 输入x 4
输出2示例 2 输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 提示 0 x 231 - 1 思路 题目让我们求一个大于等于0整数的算术平方根并且对最终结果进行向下取整。
方法一直接暴力枚举即可。
代码实现
class Solution {// 暴力枚举public int mySqrt(int x) {if (x 0 || x 1) { // 排除特殊情况return x;}for (long i 1; i x; i) {if (i * i x) {return (int)i;} else if (i * i x) {return (int)i-1;}}return -1; // 这里只是过审}
}
注意由于最后面的 return -1只是为了让我们的代码编译通过并不起实际的作用。
我们前面的暴力枚举就是把 [1x] 之间的数据按照升序的方式挨个使了个遍。 从这里我们就可以使用二分查找算法了。 其实我们最终的目的就是为了找到大于或者的结果然后再让大于的-1等于的不变而这些只能让 target 和 left 在一起。
代码实现
class Solution {// 二分查找public int mySqrt(int x) {if (x 0 || x 1) { // 排除特殊情况return x;}long left 1;long right x;// 最终的结果是向下取整的即 是合法区域的while (left right) {long mid left (right-left1) / 2;if (mid*mid x) {right mid-1;} else {left mid;}}// 找到了return (int)left;}
}
注意
1、数据量是比较大的因此相乘的结果会溢出我们得用 long类型来接收。
2、这里的二分查找是不能使用第一道题的那种的。
其实没弄明白也没关系这里反正就两种情况可以直接去套用再不济暴力枚举总可以了吧。
总结
1、对于查找固定的数据的情况可以使用第一题中的二分查找方法根据要查找的结果进行比较分为三种情况——大于、等于、小于。
2、对于范围(区间)查找和不确定性查找的情况可以使用我们后面画图推出来的二分查找根据查找的结果进行比较分为两种情况——合法区域、非法区域根据要查找的数据进行分区然后再分别更新 left 和 right——合法的一定要确保依旧存在于合法区域非法的要确保有希望调到合法区域。再就是计算中点的方式和循环条件的确定都是由 left 和 right 的变化来决定的具体可见图。
我们以后常用的也是第二种二分查找的方法。
好啦本期 二分查找算法专题1的学习之旅就到此结束啦我们下一期再一起学习吧
