二分与排序简单2 种解法
#704二分查找
在严格升序数组中查找 target，存在则返回下标，否则返回 -1。
#数组#二分查找
原题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
示例 2:
输入:nums= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不存在nums中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
解题主线
- 闭区间写法始终维护答案若存在则位于 [left, right]，循环条件必须是 left <= right。
解法 1：迭代二分
比较中点后排除不可能包含目标的一半闭区间。
-
时间复杂度： O(log n)
-
空间复杂度： O(1)
final class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 闭区间不变量：target 若存在，始终位于 [left, right]
while (left <= right) {
// 差值写法避免 left + right 发生整数溢出
int middle = left + (right - left) / 2;
if (nums[middle] == target) return middle;
// middle 已比较过，收缩时必须将其排除
if (nums[middle] < target) left = middle + 1;
else right = middle - 1;
}
return -1;
}
}解法 2：递归二分
递归传递仍可能包含目标的闭区间，区间为空时失败。
-
时间复杂度： O(log n)
-
空间复杂度： O(log n)，递归栈
final class Solution {
public int search(int[] nums, int target) {
return search(nums, target, 0, nums.length - 1);
}
private int search(int[] nums, int target, int left, int right) {
// 闭区间为空时说明所有候选位置均已排除
if (left > right) return -1;
int middle = left + (right - left) / 2;
if (nums[middle] == target) return middle;
// 递归只传递仍可能包含 target 的半侧，并排除已比较的 middle
if (nums[middle] < target) return search(nums, target, middle + 1, right);
return search(nums, target, left, middle - 1);
}
}边界与易错点
- 中点使用 left + (right - left) / 2 避免加法溢出。
- Q074_binarySearch 的题意实际是 LeetCode 704，不是 74，已与 Q704 合并。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q074_binarySearch.javaeasy/Q704_binarysearch.java