1. 二分搜索的概念
二分查找是一种在有序数组中查找某一特定元素的搜索算法。
二分查找的原理是，将目标元素和查找范围的中间值做比较，如果目标元素等于中间值，则查找结束；如果目标元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这样每一次比较都使搜索范围缩小一半。
2. 在有序数组中查找 num 是否存在
需求
给定一个有序数组
arr, 给定一个目标值target, 查找target在arr中是否存在.思路
对于有序数组中的数值查找, 首先想到使用二分法实现.
关键代码
/** * 查找target在arr中是否存在 * * @param arr 有序数组 * @param target 目标值 * @return true:表示target在arr中存在, false表示不存在 */ public static boolean exist(int[] arr, int target) { if (arr == null || arr.length == 0) { // 当数组为空时,无需查找,返回false. return false; } int L = 0; // 查找范围区间左侧的元素的下标,从0开始 int R = arr.length - 1; // 查找范围区间右侧元素的下标,从arr的末尾开始 int M = 0; // 中间元素的位置,默认是0 // <= 表示这是一个 [左闭,右闭] 的区间范围. // 不使用 < 是考虑到在查找的过程中会动态调整L和R的值,有可能出现 L和R 重合的情况,即区间范围只有一个值的情况. while (L <= R) { M = (L + R) / 2; // 获取查询区间的中点 // 下面这种方式计算结果与上面相同,但是可以避免 L + R 溢出的问题 // M = L + ((R-L)>>1); if (arr[M] == target) { // 中点的值正好等于target,找找到了该元素,返回true. return true; } else if (arr[M] < target) { // 目标值大于中点的值,则从中点+1的位置往右查找 L = M + 1; } else { // 目标值小于中点的值,则从中点-1的位置往左查找 R = M - 1; } } // 如果while循环没有找到target,则返回false; return false; }完整测试代码
3. 在有序数组中查找 >=num 的最左位置
需求
给定一个从小到大的有序数组 arr, 给定一个目标值 target, 查找在这个数组中 >=target的 最左侧的元素的下标值.
实现思路
- 有序数组中的操作,首先考虑二分查找.找到数组中间位置的数据,比较中间值是否大于等于目标值, 如果是则表明目标值一定在中间元素的左边.此时就需要向左查找.
- 如果中间值小于目标值,则表明目标值在中间值的右边,此时就需要往右查找.
关键代码
/** * 使用二分查找法,获取 >=target 的最左边的数的下标 * * @param arr 目标数组, 例如: [1,2,3,4,5,6,7,8,9] * @param target 目标值, 例如: 2 * @return */ public static int findLeft(int[] arr, int target) { int L = 0; // 查找范围区间左侧的元素的下标,从0开始 int R = arr.length - 1; // 查找范围区间右侧元素的下标,从arr的末尾开始 int M = 0; // 中间元素的位置,默认是0 int ans = -1; // 查找到的目标值的下标,没有找到则返回-1 if (arr == null || arr.length == 0) { // 当数组为空时,无需查找,返回 -1. return ans; } while (L <= R) { // 确保查找范围区间元素数量 >=1 个 M = (L + R) / 2; // 获取查询区间的中点 // 下面这种方式计算结果与上面相同,但是可以避免 L + R 溢出的问题 // M = L + ((R-L)>>1); if (arr[M] >= target) { // 如果中点元素值 >=target 说明中点往左可能还有别的数也 >=target,此时记录下标值,继续向中点左侧找,直到找到最左边 >=target 的值. R = M - 1; // 区间往左搜小 ans = M; // 记录当前下标值 } else { // 如果中点元素值 <target, 说明目标元素在中点往右的位置,则需要向右查找 L = M + 1; } } // >=target最左边的数的下标 return ans; }完整测试代码
4. 在有序数组中查找 <=num 的最右位置
需求
给定一个从小到大的有序数组 arr, 给定一个目标值 target, 查找在arr数组中 <=target 的最右侧(最大)的元素的下标值.
思路
- 有序数组中的操作,首先考虑二分查找.找到数组中间位置的数据,比较中间值是否小于等于目标值, 如果是则表明目标值一定在中间元素的右边.此时就需要向右查找.
- 如果中间值大于目标值,则表明目标值在中间值的左边,此时就需要往左查找.
关键代码
/** * 使用二分查找，数组arr中 <=num 最右边的数的下标值 * * @param arr 从小到大的有序数组 * @param target 要查询的目标值 * @return */ public static int findRight(int[] arr, int target) { int L = 0; // 数组中查找的左侧区间范围，从0开始 int R = arr.length - 1; // 数组中查找的右侧区间范围,从数组的末尾开始 int M = 0; // 初始中间位置 int ans = -1; // 响应结果,-1表示没有找到该元素 if (arr == null || arr.length == 0) { // 数组为空,不再继续查找 return ans; } while (L <= R) { // 确保查找范围区间元素数量 >=1 个 M = L + (R - L) / 2; // 获取中间位置 if (arr[M] <= target) { // 中间值与目标值进行比较,如果<=target,则标记下当前位置,继续向右查找,如果 >target则向左继续查找 ans = M; // 标记当前下标 L = M + 1; // 左侧查询区间移动到 M+1 位置,继续往右查找 } else { R = M - 1; // 右侧查询区间移动到 M-1 位置,继续往左查找 } } // 返回查询结果 return ans; }完整测试代码
5. 无序数组使用二分法寻找峰值
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
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 (数组长度在 1~1000范围内)
- -231 <= nums[i] <= 231-1 (数组元素值不超过int最大值)
- 对于所有有效的 i 都有 nums[i] != nums[i + 1] (数组中任意相邻的两个数不相等)
思路
虽然寻找峰值这样的题目,不是在有序数组中,但具体题目的要求,依然可以使用二分查找解决这个问题.
如果一个数组中存在峰值,那么从这个数组的第0个位置到最后一个位置所经过的数值,连成线一定是时高时低(想象着把数值连城折线图).
可以先从中间位置开始找峰值, 如果中间位置的数比左右两侧的数都要大,则找到峰值.
如果中间位置比左侧的数据小,则表示在左边一定至少存在一个峰值. 因为哪怕是最极端的情况, 从0位置到中间位置数据是逐个减小的,那么0位置就是峰值. 所以至少会有一个峰值. 按照这个思路继续使用二分法向左边查找峰值,直到找到一个峰值.
如果中间位置比右侧的数据小,则表示在右边至少存在一个峰值,理由和上一条相同.
关键代码
/** * 使用二分查找,找到数组中的峰值 * @param arr 数组 * @return */ public static int findPeak(int[] arr) { int n = arr.length; // 数组的长度 if (n == 1) { // 数组长度为1,那么这个元素就是峰值,因为: arr[-1] = arr[n] = 无穷小 return 0; } if (arr[0] > arr[1]) { // 满足条件: arr[-1] = 无穷小 return 0; } if (arr[n - 1] > arr[n - 2]) { // 满足条件: arr[n] = 无穷小 return n - 1; } int L = 1; // 二分查找的左侧区间范围, 从 1 开始 int R = n - 2; // 二分查找的右侧区间范围, 从 n-2 开始 int M = 0; // 中间索引,默认:0 int ans = -1; // 峰值所在位置索引 while (L <= R) { M = L + ((R - L) / 2); // 计算中间值索引 if (arr[M + 1] > arr[M]) { // M到n-1区域一定存在峰值,向右查找 L = M + 1; } else if (arr[M - 1] > arr[M]) { // 0到M区域一定存在峰值,向左查找 R = M - 1; } else { ans = M; // 找到峰值, 跳出循环 break; } } return ans; }测试地址
6. 技巧
- 二分查找需要根据左右两个查询区间找到中间位置的下标, 但是当查询范围特别大时,比如数组长度: 231 , 左右区间相加就会溢出,导致计算出错. 为了避免数值溢出, 不能使用
(L+R)/2的方式计算中间值, 需要用L+(R-L)/2的方式. - L + ((R-L) >> 1) 也等同于 L+(R-L)/2 , 样做是利用了位运算 >> 的特点, 右移1位, 就等于除以2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 george_95@126.com