本文参考 二分查找 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
基本概念
- 前提条件：
- 数组必须是有序的（升序或降序均可）。
- 核心思想：
- 每次比较中间元素与目标元素的关系，将查找区间一分为二。根据目标元素与中间元素的大小关系，决定接下来查找的区间是左半部分还是右半部分。
- 通过不断折半，缩小查找范围，最终可以在对数时间复杂度内找到目标元素（如果存在的话）。
模板I
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
题目1：x的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
方法1：二分查找
class Solution {
public int mySqrt(int x) {
int left = 0, right = x, ans = -1;
while(left <= right){
int mid = left + ( right - left) / 2;
if((long) mid * mid <= x ){
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
public static void main(String[] args) {
Solution obj = new Solution();
int x = 2147395599;
int result = obj.mySqrt(x);
System.out.println(result);
}
}
注意：
int通常占用 4 字节（32 位），表示的范围是从 -2,147,483,648 到 2,147,483,647。long通常占用 8 字节（64 位），表示的范围是从 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807。
时间复杂度：O(logx)，即为二分查找需要的次数。
空间复杂度：O(1)。
题目2：搜索旋转排序字母
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
方法1：二分查找
核心思路：
定理一：只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。
定理二：判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间。
定理三：每次二分都会至少存在一个顺序区间。
class Solution {
// search 函数：在旋转排序数组中查找目标元素
public int search(int[] nums, int target) {
int n = nums.length; // 获取数组的长度
if (n == 0) { // 如果数组为空，直接返回 -1
return -1;
}
if (n == 1) { // 如果数组只有一个元素，直接判断是否等于目标值
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1; // 初始化左右指针
// 使用二分查找算法
while (l <= r) {
int mid = l + (r - l) / 2; // 计算中间位置，避免溢出
if (nums[mid] == target) { // 如果中间元素是目标值，返回其索引
return mid;
}
// 判断左半部分是否是有序的
if (nums[0] <= nums[mid]) {
// 如果目标值在左半部分有序的范围内
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1; // 目标值在左边，调整右指针
} else {
l = mid + 1; // 目标值不在左半部分，调整左指针
}
} else {
// 如果右半部分是有序的
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1; // 目标值在右半部分，调整左指针
} else {
r = mid - 1; // 目标值不在右半部分，调整右指针
}
}
}
return -1; // 如果循环结束仍未找到目标值，返回 -1
}
// main 函数：用于测试
public static void main(String[] args) {
Solution obj = new Solution(); // 创建 Solution 类的对象
int[] nums = {4, 5, 6, 7, 0, 1, 2}; // 旋转排序数组
int target = 0; // 要查找的目标值
int result = obj.search(nums, target); // 调用 search 函数查找目标值
System.out.println(result); // 输出目标值的索引，如果未找到则输出 -1
}
}
时间复杂度：O(logx)，即为二分查找需要的次数。
空间复杂度：O(1)。
模板II
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.length && nums[left] == target) return left;
return -1;
}
题目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：二分查找
考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
class Solution {
// findMin 函数：用于在旋转排序数组中找到最小值
public int findMin(int[] nums) {
int low = 0; // 初始化左指针为数组的起始位置
int high = nums.length - 1; // 初始化右指针为数组的结束位置
// 使用二分查找的方式，查找旋转数组中的最小值
while (low < high) {
int point = low + (high - low) / 2; // 计算中间索引，避免溢出
// 如果中间值小于右边界值，说明最小值在左半部分（包括中间值）
if (nums[point] < nums[high]) {
high = point; // 右指针向左移动
} else {
// 如果中间值大于右边界值，说明最小值在右半部分
low = point + 1; // 左指针向右移动
}
}
// 最终，low 指向的就是最小值的位置
return nums[low];
}
// main 函数：用于测试
public static void main(String[] args) {
Solution obj = new Solution(); // 创建 Solution 类的对象
int[] nums = { 5, 1, 2, 3, 4 }; // 旋转排序数组
int result = obj.findMin(nums); // 调用 findMin 函数查找最小值
System.out.println(result); // 输出最小值
}
}
模板III
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
题目1：在排序数组中找到起始位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
方法1：二分查找
采用的是模板I，其实什么模板都不重要。
class Solution {
public int[] searchRange2(int[] nums, int target){
int left = 0, right = nums.length - 1;
int first = -1, last = -1;
// 找第一个target位置
while (left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] == target){
first = middle;
right = middle - 1; // 重点
} else if (nums[middle] > target) {
right = middle - 1;
}else {
left = middle + 1;
}
}
// 找最后一个target位置
left = 0;
right = nums.length - 1;
while (left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] == target){
last = middle;
left = middle + 1; // 重点
} else if (nums[middle] > target) {
right = middle - 1;
}else {
left = middle + 1;
}
}
return new int[]{first, last};
}
public static void main(String[] args) {
Solution obj = new Solution();
int[] nums = { 1, 1, 2, 2, 3, 3, 3, 4, 5, 9};
int target = 3;
int[] result = obj.searchRange2(nums,target);
System.out.println(result[0]+" "+result[1]);
}
}