算法练习-二分查找
1 代码实现
1.1 非递归实现
public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (a[mid] == value) {return mid;} else if (a[mid] < value) {low = mid + 1} else {high = mid - 1;}}return -1;
}
1.2 递归实现
public int bsearch_r(int[] a, int n, int value) {return bsearch(a, 0, n - 1, value);
}public int bsearch(int[] a, int low, int high, int value) {if (low > high) return -1;int mid = (low + high) / 2;if (a[mid] == value) {return mid;} else if (a[mid] < value) {return bsearch(a, mid + 1, high, value);} else {return bsearch(a, low, mid - 1, value);}
}
2 解题技巧
二分查找的正确姿势：
- 查找区间永远是闭区间[low, high]
- 循环条件永远是:low < high
- 对于low == high的情况，必要的时候特殊处理，在while内部补充退出条件
- 返回值永远是mid，不是low、high
- low、high的更新永远是low = mid + 1 和 high = mid - 1
- 对于非确定性查找，使用前后探测法来确定搜索区间
- 先处理命中目标，再处理左右半部分查找的情况
3 查找第一个等于x、最后一个等于x的元素
3.1 查找第一个等于x的元素
public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) {if ((mid == 0) || (a[mid - 1] != target)) return mid;else high = mid - 1;} else if (a[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;
}
3.2 查找最后一个等于x的元素
public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) {if ((mid == n - 1) || (a[mid + 1] != target)) return mid;else low = mid + 1;} else if (a[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;
}
4 查找第一个大于等于x，最后一个小于等于x的数
4.1 查找第一个大于等于x的数
public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] >= target) {if ((mid == 0) || (a[mid - 1] < target)) return mid;else high = mid - 1;} else {low = mid + 1;}}return -1;
}
4.2 查找最后一个小于等于x的数
public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if ((mid == n - 1) || (a[mid + 1] > target)) return mid;else low = mid + 1;} else {high = mid - 1;}
}
return -1;
}
5 循环有序数组中查找元素x
public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) return mid;else if (a[low] <= a[mid]) {if (target >= a[low] && target < a[mid]) {high = mid - 1;} else {low = mid + 1;}} else {if (target > a[mid] && target <= a[high]) {low = mid + 1;} else {high = mid - 1;}}}return -1;
}
6 循环有序数组查找最小值
public int bsearch(int[] a, int n) {int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (low == high) return mid;if ((mid != 0 && a[mid] < a[mid - 1]) || (mid == 0 && a[mid] < a[high]) {return mid;} else if (a[mid] > a[high]) {low = mid + 1;} else {high = mid - 1;}}return -1;
}
7 查找峰值
链接：https://leetcode.cn/problems/find-peak-element
7.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]
7.2 题解
class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int low = 0;int high = n - 1;while (low <= high) {int mid = (high + low) / 2;if (mid == 0) {if (n == 1) return 0;else if (nums[mid] > nums[mid + 1]) return mid;else low = mid + 1;} else if (mid == n - 1) {if (nums[mid] > nums[mid - 1]) return mid;else high = mid - 1;} else if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {return mid;} else if (nums[mid] > nums[mid - 1]) {low = mid + 1;} else {high = mid - 1;}}return 0;}
}
8 x的平方根
链接：https://leetcode.cn/problems/sqrtx
8.1 题目
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
8.2 题解
class Solution {public int mySqrt(int x) {if (x == 0) return 0;int low = 1;int high = x / 2 + 1;while (low <= high) {int mid = low + (high - low) / 2;long mid2 = (long)mid * mid;if (mid2 <= x) {long mid22 = ((long)mid + 1) * (mid + 1);if (mid22 <= x) {low = mid + 1;} else {return mid;}} else {high = mid - 1; }}return -1;}
}
