LeetCode 解题思路 33（Hot 100）

解题思路：

1. 左边界查找​​：

• 初始化指针和开始位置 left、right、start。在 left <= right 的条件下循环：
• 计算中间索引 mid，避免整数溢出（mid = left + (right - left) / 2）。
• 若中间元素等于目标值，记录当前位置并继续向左半部分搜索。
• 若中间元素小于目标值，说明目标值在右半部分，更新 left = mid + 1。
• 若中间元素大于目标值，说明目标值在左半部分，更新 right = mid - 1。

2. 右边界查找：

• 初始化指针和结束位置 left、right、end。在 left <= right 的条件下循环：
• 计算中间索引 mid，避免整数溢出（mid = left + (right - left) / 2）。
• 若中间元素等于目标值，记录当前位置并继续向右半部分搜索。
• 若中间元素小于目标值，说明目标值在右半部分，更新 left = mid + 1。
• 若中间元素大于目标值，说明目标值在左半部分，更新 right = mid - 1。

Java代码：

class Solution {public int[] searchRange(int[] nums, int target) {int start = binarySearchLeft(nums, target);if (start == -1) return new int[]{-1, -1};int end = binarySearchRight(nums, target);return new int[]{start, end};}private int binarySearchLeft(int[] nums, int target) {int left = 0;int right = nums.length - 1;int start = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {start = mid;right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return start;}private int binarySearchRight(int[] nums, int target) {int left = 0;int right = nums.length - 1;int end = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {end = mid;left = mid + 1;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return end;}
}

复杂度分析：

• 时间复杂度： O(logn)。两次二分查找各消耗 O(logn) 时间，总体仍为O(logn)。
• 空间复杂度： O(1)。仅使用了常数额外空间。
  

解题思路：

1. 二分查找​​： 初始化指针 left 和 right，计算中间位置 mid 循环查找。
2. 检查中点​​： 若 nums[mid] 等于目标值，直接返回 mid。
3. 判断左半段是否有序​​： 若 nums[left] <= nums[mid]，说明左半段有序。若目标值在 (nums[left], nums[mid]) 范围内，则在左半段继续搜索，否则转向右半段。
4. 判断右半段是否有序​​： 若左半段无序，则右半段必然有序。若目标值在 (nums[mid], nums[right]) 范围内，则在右半段继续搜索，否则转向左半段。

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) {return mid;} else if (nums[left] <= nums[mid]) {if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}

复杂度分析：

• 时间复杂度： O(log n)。每次二分将搜索范围缩小一半。
• 空间复杂度： O(1)。仅使用常数额外空间。