武进网站建设平台,wordpress 免费中文模板下载,网站建设能赚很多钱,南宁大型网站建设文章目录 前言什么是二分查找算法1.二分查找1.1 题目要求1.2 做题思路1.3 Java代码实现 2.在排序数组中查找元素的第一个和最后一个位置2.1 题目要求2.2 做题思路2.3 Java代码实现 3.搜索插入位置3.1 题目要求3.2 做题思路3.3 Java代码实现 4.x的平方根4.1 题目要求4.2 做题思路… 文章目录 前言什么是二分查找算法1.二分查找1.1 题目要求1.2 做题思路1.3 Java代码实现 2.在排序数组中查找元素的第一个和最后一个位置2.1 题目要求2.2 做题思路2.3 Java代码实现 3.搜索插入位置3.1 题目要求3.2 做题思路3.3 Java代码实现 4.x的平方根4.1 题目要求4.2 做题思路4.3 Java代码实现 5.山脉数组的峰顶索引5.1 题目要求5.2 做题思路5.3 Java代码实现 6.寻找峰值6.1 题目要求6.3 做题思路6.4 Java代码实现 7.寻找旋转数组中的最小值7.1 题目要求7.2 做题思路7.3 Java代码实现 总结 前言
在生活中我们往往会遇到在数组中查找某个确定的元素的时候通常我们会选择使用暴力解法这样虽然简单但是时间复杂度是O(N)时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢答案是肯定的当我们可以将数组分为两个部分的时候也就是数组具有二段性的时候可以使用二分查找的算法来进行高效的查找。通常二分查找的时间复杂度为O(logN)。那么这篇文章我将为大家分享关于二分查找的知识。
什么是二分查找算法
二分查找算法Binary Search Algorithm是一种在有序数组但不仅限于有序数组中查找特定元素的搜索算法。它采用分治策略每次比较数组中间的元素如果该元素等于目标值则搜索结束否则根据目标值与中间元素的大小关系将搜索范围缩小为数组的左半部分或右半部分然后在新的搜索范围内重复执行上述操作直到找到目标值或确定目标值不存在于数组中。
二分查找算法的时间复杂度为O(log n)其中n为数组的长度。由于每次都能排除一半的元素因此算法的效率非常高尤其适用于大规模数据的查找操作。
其实二分查找算法本来并不难只是实现二分查找算法时需要注意一些细节例如处理数组边界、处理相等的情况等。如果没有处理好边界和相等问题的时候很容易造成死循环。
1.二分查找
https://leetcode.cn/problems/binary-search/
1.1 题目要求
给定一个 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) {}
}1.2 做题思路
因为这道题目给的数组是有序的我们 定义两个变量 left 和 right 分别从数组的开头和末尾开始求 left 和 right 和的平均值的下标 mid 然后看 mid 下标所代表的值与 target 的关系如果 nums[mid] target 则可以确定在 [mid,right] 之间没有我们要找的 target 值所以直接将这一半的数据给“舍弃”将 right 的值更改为 mid - 1如果 nums[mid] target则说明在 [left,mid] 这一范围内没有我们需要找的 target 值将这一部分给“舍弃”left 的值更新为 mid 1如果nums[mid] target则返回 mid 的下标。 当然这只是一种确定区间的方法也可简单的称为“左闭右闭”还有“左闭右开、“左开右闭”这两种确定区间的方法这两种方法是差不多的那么就以“左闭右开”这种方式为大家介绍一下。我们前面为大家说明的是“左闭右闭”这种确定区间的方式左闭右闭是指left 和 right 这两个值我们都可以取到而左闭右开或者左开右闭则只是 left 或者 right 的数据可以取到。确定区间的方式不同我们最终的循环条件也不同究竟是 left right还是 left right这就取决于我们区间的确定方式如果是以“左闭右闭”的方式确定的则需要加上等号另外两种方式则不需要。 为什么呢大家可以看看下面的图。
我们就以上面所讲的基本的二分查找算法来看看这道题目该怎么做。
1.3 Java代码实现
class Solution {//这里使用的”左闭右闭“的区间确定方式public int search(int[] nums, int target) {int left 0;int right nums.length-1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {left mid 1;}else if(nums[mid] target) {right mid - 1;}else {return mid;}}return -1;}
}求 mid 的方式有两种一种是 left (right - left) / 2一种是 left (right - left 1) / 2这两种求 mid 的方式在这道题目是没什么区别的具体的区别在后面的题目会遇到。 但是为什么我们不直接用 mid (right - left) / 2 呢因为我们不知道数组的大小为多少很可能会造成 int 或者 long 类型不能够存储 left right的值。
2.在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
2.1 题目要求
给你一个按照非递减顺序排列的整数数组 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) {}
}2.2 做题思路
做这道题目如果使用和上面一样的思想的话时间复杂度会降到 O(N)为什么呢因为当你找到目标值之后你还需要找到这个数的起始位置和结束位置假设我们想要找的数是3而数组中的数字全是3的话那么就需要遍历整个数组一遍时间复杂度就会降到 O(N)所以我们也就不能使用跟上面一样的思路也就是朴素二分法这道题需要我们使用到非朴素的二分算法朴素算法其实是将数组分成了三个部分小于目标值的部分等于目标值的部分和大于目标值的部分而非朴素算法则是真正的将数组分成了两个部分小于等于目标值的部分和大于目标值的部分或者是小于目标值的部分和大于等于目标值的部分。这道题就是非朴素算法的思路将数组分为了两个部分。 寻找左边界的时候如果 nums[mid] target 则说明 mid 在小于目标值的那一部分这部分肯定没有我们需要的数字所以将 left 改为 mid 1而如果 numd[mid] target 的时候就不能将 right 改为 mid - 1了因为这个 mid 值可能刚好是我们需要找的值所以将 right 的值改为 mid 而不是 mid - 1
在寻找有边界的时候数组被分为了小于等于和大于目标值的两部分当 nums[mid] target 的时候因为 mid 所指向的位置可能是我们要找的值所以 left mid当 nums[mid] target 的值因为在 [mid,righ] 之间肯定没有我们想要找的值所以right mid - 1.
数组分为不同的两部分求 mid 的方法也是不同的这也就是上面说的 mid left (right - left) / 2 和 mid left (right - left 1) / 2的区别。
注意了循环条件一定不能加等号因为当left right的时候这个相遇的值恰好是我们需要的值所以没必要多判断一次更重要的是会陷入死循环。
2.3 Java代码实现
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret new int[]{-1,-1};int n nums.length;if(n 0) return ret; //当数组大小为0时直接返回int left 0;int right n - 1;//求目标值的第一个位置while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {left mid 1;}else {right mid;}}if(nums[left] target) ret[0] left; //判断数字中是否存在目标值right n - 1;//求目标值的最后一个位置while(left right) {int mid left (right - left 1) / 2;if(nums[mid] target) {right mid - 1;}else {left mid;}}if(nums[left] target) ret[1] left;return ret;}
}3.搜索插入位置
https://leetcode.cn/problems/search-insert-position/
3.1 题目要求
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
class Solution {public int searchInsert(int[] nums, int target) {}
}3.2 做题思路
根据题目我们可以知道这个题目大致分为两种情况目标值在数组中返回目标值的下标如果目标值不存在则返回目标值应该插入位置的下标。
可以将数组分为两个部分这就可以用到我们的二分查找算法了。
3.3 Java代码实现
class Solution {public int searchInsert(int[] nums, int target) {int n nums.length;int left 0;int right n - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {left mid 1;}else {right mid;}}if(nums[left] target) return left 1; //当待插入位置位于数组的末尾时需要作出判断else return left;}
}4.x的平方根
https://leetcode.cn/problems/sqrtx/
4.1 题目要求
给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4
输出2示例 2
输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。提示
0 x 231 - 1
class Solution {public int mySqrt(int x) {}
}4.2 做题思路
如果 x 的平方根为整数的话则直接返回如果不是整数的话则返回平方小于 x 的最大整数通过这样理解题目我们也可以将数组分为两个部分小于等于 x 的部分和大于 x 的部分。同样使用二分查找的算法解决。 4.3 Java代码实现
class Solution {public int mySqrt(int x) {long left 0; //这里mid * mid可能会很大超出 int 所能表示的范围所以我们用 long 来表示long right x;while(left right) {long mid left (right - left 1) / 2;if(mid * mid x) {right mid - 1;}else {left mid;}}return (int)left;}
}5.山脉数组的峰顶索引
https://leetcode.cn/problems/peak-index-in-a-mountain-array/
5.1 题目要求
符合下列属性的数组 arr 称为 山脉数组
arr.length 3存在 i0 i arr.length - 1使得 arr[0] arr[1] … arr[i-1] arr[i] arr[i] arr[i1] … arr[arr.length - 1] 给你由整数组成的山脉数组 arr 返回满足 arr[0] arr[1] … arr[i - 1] arr[i] arr[i 1] … arr[arr.length - 1] 的下标 i 。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1
输入arr [0,1,0]
输出1示例 2
输入arr [0,2,1,0]
输出1示例 3
输入arr [0,10,5,2]
输出1提示
3 arr.length 1050 arr[i] 106题目数据保证 arr 是一个山脉数组
class Solution {public int peakIndexInMountainArray(int[] arr) {}
}5.2 做题思路
因为题目保证数组 arr 是一个山脉数组有很明显的二段性所以很容易想到二分查找的算法。 将数组分为两部分小于峰顶值的部分和大于等于峰顶值的部分。当 mid 落在小于峰顶值的部分时我们使 left mid 1如果 mid 落在 大于等于峰顶值的部分时令right mid。
5.3 Java代码实现
class Solution {public int peakIndexInMountainArray(int[] arr) {int left 0;int right arr.length - 1;while(left right) {int mid left (right - left) / 2;if(arr[mid] arr[mid 1]) {left mid 1;}else {right mid;}}return left;}
}6.寻找峰值
https://leetcode.cn/problems/find-peak-element/
6.1 题目要求
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] nums[n] -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1
输入nums [1,2,3,1]
输出2
解释3 是峰值元素你的函数应该返回其索引 2。示例 2
输入nums [1,2,1,3,5,6,4]
输出1 或 5
解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5 其峰值元素为 6。提示
1 nums.length 1000-231 nums[i] 231 - 1对于所有有效的 i 都有 nums[i] ! nums[i 1]
class Solution {public int findPeakElement(int[] nums) {}
}6.3 做题思路
注意看题目题目中给了可以假设 nums[-1] nums[n] 负无穷所以可以将数组看成是从负无穷加到一个峰值然后再从峰值减小到负无穷即使你数组中的元素是单调的也会形成山峰的形状很明显的二段性所以使用二分查找的算法。同样将数组分为两部分小于峰值的部分和大于等于峰值的部分。
6.4 Java代码实现
class Solution {public int findPeakElement(int[] nums) {int left 0;int right nums.length - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] nums[mid 1]) {left mid 1;}else {right mid;}}return left;}
}7.寻找旋转数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
7.1 题目要求
已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [3,4,5,1,2]
输出1
解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2
输入nums [4,5,6,7,0,1,2]
输出0
解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3
输入nums [11,13,15,17]
输出11
解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示
n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转
class Solution {public int findMin(int[] nums) {}
}7.2 做题思路
无论数组旋转多少次总会将前面部分的升序数组给旋转到后面部分数组的后面通过画图我们可以看出这又是明显的具有二段性的数组可以使用二分查找的算法来解决。 数组的两个部分中较大的部分中的所有元素都大于较小数组部分的最大值而我们要找的最小的值也就是在较小的那一部分中所以我们将数组分为大于 nums[n-1] 的部分和小于等于nums[n-1] 两部分当 mid 落在大于 nums[n-1] 的部分时left mid 1当 mid 落在小于等于 numd[n-1] 的部分时right mid。
7.3 Java代码实现
class Solution {public int findMin(int[] nums) {int n nums.length;int left 0;int right n - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] nums[n-1]) {left mid 1;}else {right mid;}}return nums[left];}
}总结
其实二分查找这个算法不算难只要主要好边界条件、区间不造成死循环其实就很简单只要知道了可以将数组分为哪两部分就可以直接套模板通过看上面几道题目的代码我们也可以看出代码基本上类似所以大家只要能够将数组分为两部分和不同部分区间的变化条件和区间的变化就可以了。
