二分查找
更新: 9/19/2025 字数: 0 字 时长: 0 分钟
搜索插入位置
java
/**
* <p>此方法解决“搜索插入位置”问题，采用经典的<strong>二分查找（Binary Search）算法</strong>。</p>
* <p>核心思想：题目要求时间复杂度为 O(log n)，且数组已排序，这明确指示我们要使用二分查找。
* 这个问题的本质是找到第一个大于或等于 {@code target} 的元素的索引。如果 {@code target} 不存在，
* 这个索引就是它的插入位置；如果 {@code target} 存在，这个索引就是它第一次出现的（或唯一存在的）位置。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化指针和答案变量：</strong>
* <ul>
* <li>{@code left = 0}：查找范围的左边界，初始为数组的第一个索引。</li>
* <li>{@code right = nums.length - 1}：查找范围的右边界，初始为数组的最后一个索引。</li>
* <li>{@code ans = nums.length}：用于记录最终的插入位置。初始化为 {@code nums.length}，
* 这是为了处理 {@code target} 大于数组中所有元素的情况（即 {@code target} 应插入到数组末尾）。</li>
* </ul>
* </li>
* <li><strong>二分查找循环：</strong>
* <ul>
* <li>{@code while (left <= right)}：当左边界小于或等于右边界时，循环继续。
* 这个条件保证了我们能够检查到 {@code left == right} 这种情况，甚至在 {@code left} 最终指向插入位置后 {@code left > right} 才结束。</li>
* <li>{@code mid = left + (right - left) / 2;}：计算中间索引。这种写法可以避免 {@code left + right} 溢出。</li>
* <li><strong>比较 {@code nums[mid]} 与 {@code target}：</strong>
* <ul>
* <li>{@code if (nums[mid] >= target)}：
* <ul>
* <li>这表示 {@code nums[mid]} <strong>可能</strong>是 {@code target} 的插入位置，或者 {@code target} 在 {@code mid} 之前（包括 {@code mid} 本身）。
* 我们找到了一个候选值，所以更新 {@code ans = mid}。</li>
* <li>由于我们寻找的是“第一个”大于或等于 {@code target} 的位置，所以我们需要尝试在左半部分继续查找更小的索引。
* {@code right = mid - 1;}</li>
* </ul>
* </li>
* <li>{@code else (nums[mid] < target)}：
* <ul>
* <li>这表示 {@code nums[mid]} 太小了，{@code target} 肯定在 {@code mid} 之后。
* 所以，在右半部分查找。</li>
* <li>{@code left = mid + 1;}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>循环结束后，{@code ans} 变量将存储 {@code target} 的正确插入位置。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log n)}。
* <ul>
* <li>二分查找在每次迭代中将搜索空间减半，因此对数时间复杂度。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量，没有额外的数据结构。</li>
* </ul>
* </li>
* </ul>
*/
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n - 1;
// 目标值不存在时，返回它将会被按顺序插入的位置
// 这个变量 ans 用来记录可能插入的位置，初始值设为 n
// 应对 target 大于所有元素的情况
int ans = n;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止 left + right 溢出
if (nums[mid] >= target) {
// 当前 mid 位置的元素大于或等于 target
// 说明 mid 可能是插入位置，或者 target 应该在 mid 的左边（包括 mid 本身）
ans = mid; // 记录当前 mid 为一个可能的答案
right = mid - 1; // 继续向左半部分查找更小的索引
} else {
// 当前 mid 位置的元素小于 target
// 说明 target 肯定在 mid 的右边
left = mid + 1; // 在右半部分查找
}
}
return ans; // 循环结束后，ans 就是目标值的插入位置
}搜索二维矩阵
java
/**
* <p>此方法解决“搜索二维矩阵”问题，采用<strong>两次二分查找</strong>的策略。</p>
* <p>核心思想：由于矩阵具备两条关键属性：
* <ol>
* <li>每行从左到右递增。</li>
* <li>每行的第一个元素大于前一行的最后一个元素。</li>
* </ol>
* <p>
* 这允许我们首先通过二分查找确定 {@code target} 可能存在于哪一行，
* 然后在该行内再进行一次二分查找来确定 {@code target} 是否存在。
* </p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理边界情况：</strong>
* <ul>
* <li>如果 {@code matrix} 为空或尺寸为 {@code 0}，直接返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>第一次二分查找 (定位行)：</strong>
* <ul>
* <li>目标：找到 {@code target} 可能所在的行。我们寻找的是第一个行首元素小于等于 {@code target} 的行。</li>
* <li>{@code m = matrix.length} (行数), {@code n = matrix[0].length} (列数)。</li>
* <li>{@code top = 0}, {@code bottom = m - 1}。</li>
* <li>{@code candidateRow = -1}：用于记录最有可能的行索引。</li>
* <li>{@code while (top <= bottom)}：
* <ul>
* <li>{@code midRow = top + (bottom - top) / 2}。</li>
* <li>{@code if (matrix[midRow][0] == target)}：如果找到，直接返回 {@code true}。</li>
* <li>{@code else if (matrix[midRow][0] < target)}：{@code target} 可能在 {@code midRow} 或其下方的行。
* <ul>
* <li>{@code candidateRow = midRow;}：记录当前行作为可能的候选行。</li>
* <li>{@code top = midRow + 1;}：继续向下方查找。</li>
* </ul>
* </li>
* <li>{@code else (matrix[midRow][0] > target)}：{@code target} 肯定在 {@code midRow} 的上方。
* <ul>
* <li>{@code bottom = midRow - 1;}：向上方查找。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>检查 {@code candidateRow} 的有效性：</strong>
* <ul>
* <li>{@code if (candidateRow == -1)}：如果没有找到任何行首元素小于 {@code target} 的行，说明 {@code target} 比所有行的首元素都小，不可能存在。返回 {@code false}。</li>
* <li>如果 {@code target} 比 {@code candidateRow} 这一行的最后一个元素都大 ({@code matrix[candidateRow][n-1] < target})，也说明 {@code target} 不可能存在于该行。返回 {@code false}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>第二次二分查找 (在确定行内定位元素)：</strong>
* <ul>
* <li>确定要在 {@code matrix[candidateRow]} 这一行中搜索。</li>
* <li>{@code rowArray = matrix[candidateRow]}。</li>
* <li>{@code left = 0}, {@code right = n - 1}。</li>
* <li>{@code while (left <= right)}：
* <ul>
* <li>{@code mid = left + (right - left) / 2}。</li>
* <li>{@code if (rowArray[mid] == target)}：找到，返回 {@code true}。</li>
* <li>{@code else if (rowArray[mid] < target)}：向右查找 {@code left = mid + 1}。</li>
* <li>{@code else (rowArray[mid] > target)}：向左查找 {@code right = mid - 1}。</li>
* </ul>
* </li>
* <li>如果循环结束仍未找到，返回 {@code false}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log m + log n)}。
* <ul>
* <li>第一次二分查找（定位行）需要 {@code O(log m)} 的时间。</li>
* <li>第二次二分查找（定位列）需要 {@code O(log n)} 的时间。</li>
* <li>总时间复杂度是两者的和。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量。</li>
* </ul>
* </li>
* </ul>
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
// --- 第一次二分查找：定位 target 可能所在的行 ---
int top = 0;
int bottom = m - 1;
int candidateRow = -1; // 记录最有可能的行索引
while (top <= bottom) {
int midRow = top + (bottom - top) / 2;
if (matrix[midRow][0] == target) {
return true; // 目标值就是某行第一个元素
} else if (matrix[midRow][0] < target) {
// 当前行首元素小于 target，target 可能在当前行或下方的行
candidateRow = midRow; // 记录当前行作为可能的候选行
top = midRow + 1; // 继续向下方查找
} else {
// 当前行首元素大于 target，target 肯定在当前行的上方
bottom = midRow - 1; // 向上方查找
}
}
// 检查 candidateRow 的有效性
if (candidateRow == -1) {
// 如果 candidateRow 仍为 -1，说明 target 比所有行的首元素都小，不可能存在
return false;
}
// 如果 target 比我们定位到的这一行的最后一个元素都大，也不可能存在于该行
if (matrix[candidateRow][n - 1] < target) {
return false;
}
// --- 第二次二分查找：在确定的行（candidateRow）内查找 target ---
int[] rowArray = matrix[candidateRow]; // 获取目标行
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (rowArray[mid] == target) {
return true; // 找到目标值
} else if (rowArray[mid] < target) {
left = mid + 1; // 向右查找
} else {
right = mid - 1; // 向左查找
}
}
return false; // 如果都没有找到，返回 false
}java
/**
* <p>此方法解决“搜索二维矩阵”问题，采用<strong>一次模拟二分查找</strong>的更高效策略。</p>
* <p>核心思想：利用矩阵的两条属性（每行递增，以及每行首元素大于前一行尾元素），
* 我们可以将整个 {@code m x n} 的二维矩阵逻辑上视为一个长度为 {@code m * n} 的一维有序数组。
* 然后，我们在这个虚拟的一维数组上执行标准的二分查找。
* 关键在于，需要将一维数组的索引映射回二维矩阵的 {@code (row, col)} 坐标。</p>
*
* <h3>索引映射关系：</h3>
* <p>对于一个 {@code m x n} 的矩阵，如果将其展平为一维数组，其索引 {@code k} (从 {@code 0} 到 {@code m*n - 1}) 与二维坐标 {@code (row, col)} 的关系为：</p>
* <ul>
* <li>{@code row = k / n} (整数除法，{@code n} 是矩阵的列数)</li>
* <li>{@code col = k % n} (取模运算，{@code n} 是矩阵的列数)</li>
* </ul>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理边界情况：</strong>
* <ul>
* <li>如果 {@code matrix} 为空或尺寸为 {@code 0}，直接返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>初始化二分查找范围：</strong>
* <ul>
* <li>{@code m = matrix.length} (行数)</li>
* <li>{@code n = matrix[0].length} (列数)</li>
* <li>{@code left = 0}：虚拟一维数组的起始索引。</li>
* <li>{@code right = m * n - 1}：虚拟一维数组的结束索引。</li>
* </ul>
* </li>
* <li><strong>二分查找循环：</strong> {@code while (left <= right)}
* <ul>
* <li>{@code mid = left + (right - left) / 2;}：计算虚拟一维数组的中间索引。</li>
* <li><strong>将 {@code mid} 映射到二维坐标：</strong>
* <ul>
* <li>{@code midRow = mid / n;}</li>
* <li>{@code midCol = mid % n;}</li>
* </ul>
* </li>
* <li><strong>比较 {@code matrix[midRow][midCol]} 与 {@code target}：</strong>
* <ul>
* <li>{@code if (matrix[midRow][midCol] == target)}：找到目标值，返回 {@code true}。</li>
* <li>{@code else if (matrix[midRow][midCol] < target)}：中间元素太小，{@code target} 肯定在 {@code mid} 的右侧。
* <ul>
* <li>{@code left = mid + 1;}</li>
* </ul>
* </li>
* <li>{@code else (matrix[midRow][midCol] > target)}：中间元素太大，{@code target} 肯定在 {@code mid} 的左侧。
* <ul>
* <li>{@code right = mid - 1;}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果循环结束仍未找到目标值，返回 {@code false}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log(m * n))}。
* <ul>
* <li>二分查找的搜索空间是 {@code m * n} 个元素，因此时间复杂度是 {@code O(log(m*n))}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量。</li>
* </ul>
* </li>
* </ul>
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
// 将二维矩阵看作一个展平的一维有序数组进行二分查找
int left = 0; // 虚拟一维数组的起始索引
int right = m * n - 1; // 虚拟一维数组的结束索引
while (left <= right) {
int mid = left + (right - left) / 2; // 计算虚拟一维数组的中间索引
// 将一维索引 mid 映射回二维矩阵的 (row, col) 坐标
int midRow = mid / n; // 行索引
int midCol = mid % n; // 列索引
if (matrix[midRow][midCol] == target) {
return true; // 找到目标值
} else if (matrix[midRow][midCol] < target) {
// 中间元素小于 target，说明 target 在 mid 的右侧
left = mid + 1;
} else {
// 中间元素大于 target，说明 target 在 mid 的左侧
right = mid - 1;
}
}
return false; // 循环结束仍未找到目标值
}::
在排序数组中查找元素的第一个和最后一个位置
java
/**
* <p>此方法解决“在排序数组中查找元素的第一个和最后一个位置”问题，
* 采用<strong>两次变种二分查找（Binary Search）</strong>的策略。</p>
* <p>核心思想：题目要求时间复杂度为 O(log n)，且数组已排序，这明确指示我们要使用二分查找。
* 由于需要找出目标的起始和结束位置，我们不能仅仅找到任意一个匹配项就停止。
* 我们需要分别找到目标值第一次出现的位置（左边界）和最后一次出现的位置（右边界）。</p>
*
* <h3>查找策略：</h3>
* <p>我们可以设计一个通用的二分查找辅助函数，该函数能够根据布尔参数返回两种情况的“插入位置”：</p>
* <ol>
* <li><strong>查找左边界 ({@code lowerBound = true})：</strong> 寻找数组中第一个<strong>大于或等于</strong> {@code target} 的元素的索引。
* 这会找到第一个 {@code target} 或应插入 {@code target} 的位置。</li>
* <li><strong>查找右边界 ({@code lowerBound = false})：</strong> 寻找数组中第一个<strong>严格大于</strong> {@code target} 的元素的索引。
* 这个索引减 {@code 1} 就是 {@code target} 最后一次出现的位置。</li>
* </ol>
*
* <h3>{@code binarySearch(nums, target, lowerBound)} 辅助函数实现：</h3>
* <ul>
* <li>{@code left = 0}, {@code right = nums.length - 1}</li>
* <li>{@code ans = nums.length}：初始化答案为 {@code nums.length}，表示 {@code target} 可能在数组末尾之外。</li>
* <li>{@code while (left <= right)}：标准二分查找循环。
* <ul>
* <li>{@code mid = left + (right - left) / 2;}</li>
* <li><strong>判断条件：</strong>
* <ul>
* <li>{@code if (nums[mid] > target || (lowerBound && nums[mid] >= target))}
* <ul>
* <li>如果 {@code nums[mid]} 严格大于 {@code target}：无论哪种查找 ({@code lowerBound} 是 {@code true} 或 {@code false})，都意味着 {@code nums[mid]} 是一个可能的答案（或 {@code target} 在其左侧）。</li>
* <li>如果 {@code lowerBound} 为 {@code true} 且 {@code nums[mid]} 等于 {@code target}：这正是我们要找的左边界，也是一个可能的答案。</li>
* <li>在这两种情况下：
* <ul>
* <li>{@code ans = mid;}：记录当前 {@code mid} 为一个候选答案。</li>
* <li>{@code right = mid - 1;}：尝试在左半部分继续寻找更小的索引（即更左的边界）。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>{@code else} ({@code nums[mid] < target} 或 {@code (!lowerBound && nums[mid] == target)})：
* <ul>
* <li>{@code nums[mid]} 太小了，或者它等于 {@code target} 但我们正在找严格大于 {@code target} 的位置。
* 这意味着 {@code target} (或其左边界) 肯定在 {@code mid} 的右边。</li>
* <li>{@code left = mid + 1;}：在右半部分查找。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li>返回 {@code ans}。</li>
* </ul>
*
* <h3>{@code searchRange(nums, target)} 主函数实现：</h3>
* <ul>
* <li>{@code int leftBound = binarySearch(nums, target, true);} // 查找第一个 {@code >= target} 的位置</li>
* <li>{@code int rightBound = binarySearch(nums, target, false) - 1;} // 查找第一个 {@code > target} 的位置，然后减 1</li>
* <li><strong>判断结果的有效性：</strong>
* <ul>
* <li>{@code if (leftBound <= rightBound && rightBound < nums.length && nums[leftBound] == target && nums[rightBound] == target)}
* <ul>
* <li>这个条件确保了：
* <ul>
* <li>{@code leftBound} 不在 {@code rightBound} 右边。</li>
* <li>{@code rightBound} 没有越界 (即 {@code target} 没有比所有元素都大)。</li>
* <li>{@code leftBound} 和 {@code rightBound} 处的元素确实是 {@code target} (避免了 {@code target} 不存在但返回值看上去有效的情况，例如 {@code [1,3], target=2} 会返回 {@code [1,-1]}，需要额外判断)。</li>
* </ul>
* </li>
* <li>如果所有条件都满足，返回 {@code [leftBound, rightBound]}。</li>
* </ul>
* </li>
* <li>{@code else}：如果上述任何条件不满足，说明 {@code target} 不存在于数组中，返回 {@code [-1, -1]}。</li>
* </ul>
* </li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log n)}。
* <ul>
* <li>进行了两次二分查找，每次都是 {@code O(log n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量。</li>
* </ul>
* </li>
* </ul>
*/
public int[] searchRange(int[] nums, int target) {
int leftBound = binarySearch(nums, target, true); // 查找第一个 >= target 的位置
int rightBound = binarySearch(nums, target, false) - 1; // 查找第一个 > target 的位置，然后减 1
// 检查找到的左右边界是否有效
// 1. leftBound <= rightBound：确保左边界不越过右边界 (例如 target 不存在时可能发生)
// 2. rightBound < nums.length：确保右边界没有超出数组范围 (例如 target 大于所有元素时)
// 3. nums[leftBound] == target && nums[rightBound] == target:
// 确保在有效的边界位置上，确实是 target。这处理了 target 不存在，但二分查找返回了看似有效的插入位置的情况。
// 例如 nums=[2, 2], target=3. leftBound=2, rightBound=1. 则 leftBound > rightBound 返回 [-1,-1]
// 例如 nums=[1, 3], target=2. leftBound=1, rightBound=0. 则 leftBound > rightBound 返回 [-1,-1]
// 例如 nums=[5, 7, 7, 8, 8, 10], target=6. leftBound=1, rightBound=0. leftBound > rightBound 返回 [-1,-1]
if (leftBound <= rightBound
&& leftBound < nums.length && rightBound < nums.length // 边界值不能是等于 nums.length 导致越界
&& nums[leftBound] == target
&& nums[rightBound] == target) {
return new int[]{leftBound, rightBound};
}
return new int[]{-1, -1};
}
/**
* 通用的二分查找辅助函数。
* 查找目标值 target 在数组中应该插入的位置 (即第一个满足条件的元素的索引)。
*
* @param nums 排序数组
* @param target 目标值
* @param lowerBound 如果为 true，查找第一个 >= target 的元素的索引 (即左边界)。
* 如果为 false，查找第一个 > target 的元素的索引 (即右边界 + 1)。
* @return 目标值应该插入的位置 (第一个满足条件的元素的索引)。
*/
private int binarySearch(int[] nums, int target, boolean lowerBound) {
int left = 0;
int right = nums.length - 1;
int ans = nums.length; // 默认答案是数组长度，表示 target 比所有元素都大，应插入到末尾
while (left <= right) {
int mid = left + (right - left) / 2; // 防止 left + right 溢出
// 判断条件：
// 如果 nums[mid] > target (无论找左边界还是右边界，都说明 target 在左边)
// 或者 lowerBound 为 true 且 nums[mid] == target (我们在找左边界，这个 mid 可能是答案)
if (nums[mid] > target || (lowerBound && nums[mid] >= target)) {
ans = mid; // 记录当前的 mid 为一个可能的答案
right = mid - 1; // 尝试在左半部分继续寻找更小的索引 (即更左的边界)
} else {
// nums[mid] < target (target 在 mid 右边)
// 或者 lowerBound 为 false 且 nums[mid] == target (我们需要找严格大于 target 的，所以 current mid 不合适，target 应该在 mid 右边)
left = mid + 1; // 在右半部分查找
}
}
return ans;
}搜索旋转排序数组
java
/**
* <p>此方法解决“搜索旋转排序数组”问题，采用经典的<strong>变种二分查找（Binary Search）算法</strong>。</p>
* <p>核心思想：尽管数组被旋转了，但它仍然由两个有序的子数组组成。
* 因此，我们仍然可以使用二分查找的思想。关键在于，在每次迭代中，
* 我们需要判断当前 {@code mid} 所在的区间是左边有序子数组还是右边有序子数组，
* 然后根据 {@code target} 的值在对应的有序区间内进行搜索。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化指针：</strong>
* <ul>
* <li>{@code left = 0}：查找范围的左边界。</li>
* <li>{@code right = nums.length - 1}：查找范围的右边界。</li>
* </ul>
* </li>
* <li><strong>二分查找循环：</strong> {@code while (left <= right)}
* <ul>
* <li>{@code mid = left + (right - left) / 2;}：计算中间索引，防止 {@code left + right} 溢出。</li>
* <li><strong>判断是否找到目标值：</strong>
* <ul>
* <li>{@code if (nums[mid] == target)}：如果找到目标值，直接返回 {@code mid}。</li>
* </ul>
* </li>
* <li><strong>判断 {@code mid} 所在的有序区间：</strong>
* <ul>
* <li><strong>情况一：左半部分 {@code nums[left...mid]} 是有序的</strong> ({@code nums[left] <= nums[mid]})
* <p>这意味着 {@code mid} 在旋转点或旋转点左侧（包含旋转点在 {@code mid} 之前）。</p>
* <ul>
* <li>{@code if (target >= nums[left] && target < nums[mid])}：
* <ul>
* <li>如果 {@code target} 落在这个有序的左半部分区间内，那么 {@code target} 肯定在 {@code mid} 的左侧。</li>
* <li>{@code right = mid - 1;}：将搜索范围缩小到左半部分。</li>
* </ul>
* </li>
* <li>{@code else}：
* <ul>
* <li>{@code target} 不在左半部分的有序区间内，那么它肯定在右半部分（包括跨越旋转点后的那段）。</li>
* <li>{@code left = mid + 1;}：将搜索范围缩小到右半部分。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>情况二：右半部分 {@code nums[mid...right]} 是有序的</strong> ({@code nums[left] > nums[mid]})
* <p>这意味着 {@code mid} 已经跨过了旋转点，位于旋转点右侧。</p>
* <ul>
* <li>{@code if (target > nums[mid] && target <= nums[right])}：
* <ul>
* <li>如果 {@code target} 落在这个有序的右半部分区间内，那么 {@code target} 肯定在 {@code mid} 的右侧。</li>
* <li>{@code left = mid + 1;}：将搜索范围缩小到右半部分。</li>
* </ul>
* </li>
* <li>{@code else}：
* <ul>
* <li>{@code target} 不在右半部分的有序区间内，那么它肯定在左半部分（包括跨越旋转点前的那段）。</li>
* <li>{@code right = mid - 1;}：将搜索范围缩小到左半部分。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果循环结束后仍未返回，说明 {@code target} 不存在于数组中，返回 {@code -1}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log n)}。
* <ul>
* <li>每一步二分查找都将搜索空间减半。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量。</li>
* </ul>
* </li>
* </ul>
*/
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间索引
if (nums[mid] == target) {
return mid; // 找到目标值，返回其索引
}
// 判断哪一部分是有序的
if (nums[left] <= nums[mid]) { // 左半部分 (从 nums[left] 到 nums[mid]) 是有序的
// 检查 target 是否在有序的左半部分中
if (target >= nums[left] && target < nums[mid]) {
// target 在左半部分，将搜索范围缩小到左侧
right = mid - 1;
} else {
// target 不在左半部分，说明在右半部分（无序或有序）
left = mid + 1;
}
} else { // 右半部分 (从 nums[mid] 到 nums[right]) 是有序的
// 检查 target 是否在有序的右半部分中
if (target > nums[mid] && target <= nums[right]) {
// target 在右半部分，将搜索范围缩小到右侧
left = mid + 1;
} else {
// target 不在右半部分，说明在左半部分（无序或有序）
right = mid - 1;
}
}
}
return -1; // 循环结束仍未找到目标值
}寻找旋转排序数组中的最小值
java
/**
* <p>此方法解决“寻找旋转排序数组中的最小值”问题，采用经典的<strong>变种二分查找（Binary Search）算法</strong>。</p>
* <p>核心思想：旋转排序数组由两个有序的子数组组成，最小值是这两个子数组的连接点。
* 这个最小值有以下特性：它是数组中唯一一个比其右边元素小（除非它是最后一个元素）
* 且比其左边元素大（除非它是第一个元素）的“局部最低点”。
* 更直观地，它是唯一一个小于数组第一个元素 {@code nums[0]} 的元素（如果是旋转过的话）。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理边界情况：</strong>
* <ul>
* <li>如果 {@code nums} 为空或长度为 {@code 0}，根据题目一般默认不考虑，或者返回一个约定值（例如 {@code Integer.MIN_VALUE} 或抛异常），
* 但在 LeetCode 中，数组通常至少包含一个元素。</li>
* </ul>
* </li>
* <li><strong>处理未旋转的情况：</strong>
* <ul>
* <li>{@code if (nums[0] <= nums[nums.length - 1])}：
* <ul>
* <li>如果数组的第一个元素小于或等于最后一个元素，说明数组没有被旋转（或者旋转了 {@code n} 次）。</li>
* <li>此时数组本身就是升序的，最小值就是第一个元素 {@code nums[0]}。直接返回。</li>
* </ul>
* <p>例如：{@code [11,13,15,17]} 或 {@code [0,1,2,4,5,6,7]}。</p>
* </li>
* </ul>
* </li>
* <li><strong>初始化指针：</strong>
* <ul>
* <li>{@code left = 0}：查找范围的左边界。</li>
* <li>{@code right = nums.length - 1}：查找范围的右边界。</li>
* </ul>
* </li>
* <li><strong>二分查找循环：</strong> {@code while (left < right)}
* <ul>
* <li>{@code mid = left + (right - left) / 2;}：计算中间索引，防止 {@code left + right} 溢出。</li>
* <li><strong>判断 {@code mid} 所在的区间：</strong>
* <ul>
* <li>{@code if (nums[mid] < nums[right])}：
* <ul>
* <li>这表示从 {@code mid} 到 {@code right} 的这段子数组是<strong>有序且递增</strong>的。</li>
* <li>由于 {@code nums[mid]} 小于 {@code nums[right]}，这意味着 {@code mid} 可能是最小值，或者最小值在 {@code mid} 的左侧。</li>
* <li>因此，将右边界 {@code right} 更新为 {@code mid}。</li>
* <p>例如：{@code [4,5,1,2,3]}, {@code L=0, R=4, M=2, nums[M]=1}. {@code nums[M] (1) < nums[R] (3)}. 最小值在 {@code [L, M]} 范围内，{@code R = M} (即 {@code 2}).</p>
* </ul>
* </li>
* <li>{@code else} ({@code nums[mid] > nums[right]})：
* <ul>
* <li>这表示从 {@code mid} 到 {@code right} 的这段子数组是<strong>非有序</strong>的（跨越了旋转点）。</li>
* <li>由于 {@code nums[mid]} 大于 {@code nums[right]}，这意味着 {@code mid} 肯定不在递增的那一段开头，而是位于较大的部分。
* 最小值肯定在 {@code mid} 的右侧，包括 {@code mid+1} 及其之后。</li>
* <li>因此，将左边界 {@code left} 更新为 {@code mid + 1}。</li>
* <p>例如：{@code [3,4,5,1,2]}, {@code L=0, R=4, M=2, nums[M]=5}. {@code nums[M] (5) > nums[R] (2)}. 最小值在 {@code [M+1, R]} 范围内，{@code L = M+1} (即 {@code 3}).</p>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>循环结束后，{@code left} ({@code right} 也等于 {@code left}) 将指向数组中的最小元素。返回 {@code nums[left]}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(log n)}。
* <ul>
* <li>二分查找在每次迭代中将搜索空间减半。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数级别的变量。</li>
* </ul>
* </li>
* </ul>
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
// 根据题目一般测试用例不会是空数组，但作为健壮性考虑
throw new IllegalArgumentException("Array cannot be empty or null.");
}
int n = nums.length;
// 如果数组没有旋转（或者旋转了 n 次），最小值就是第一个元素
// 这种情况特点是 nums[0] <= nums[n-1]
// 例如 [1,2,3,4,5] 或者 [11,13,15,17]
if (nums[0] <= nums[n - 1]) {
return nums[0];
}
int left = 0;
int right = n - 1;
// 当 left < right 时进行循环，最终 left 和 right 会指向最小值
while (left < right) {
int mid = left + (right - left) / 2; // 计算中间索引
// 比较 nums[mid] 和 nums[right] 来判断哪部分是有序的
if (nums[mid] < nums[right]) {
// 如果 nums[mid] < nums[right]，说明 mid 到 right 是一个有序的子数组。
// 最小值可能在 left 到 mid 之间 (包含 mid 本身)，或者 mid 就是最小值。
// 例如 [4,5,1,2,3]，mid=2, nums[mid]=1, nums[right]=3.
// 1 < 3，所以最小值在左半部分或就是 mid。
right = mid; // 将右边界缩小到 mid
} else { // nums[mid] > nums[right]
// 如果 nums[mid] > nums[right]，说明 mid 到 right 这一段是跨越了旋转点的。
// 此时，最小值一定在 mid 的右侧 (mid+1 到 right 之间)。
// 例如 [3,4,5,1,2]，mid=2, nums[mid]=5, nums[right]=2.
// 5 > 2，所以最小值在右半部分。
left = mid + 1; // 将左边界缩小到 mid + 1
}
}
// 循环结束时，left (和 right) 就会指向最小元素的索引
return nums[left];
}寻找两个正序数组的中位数
java
/**
* TODO
*/贡献者
LI SIR