二分与排序简单2 种解法
#704二分查找
在严格升序数组中查找 target，存在则返回下标，否则返回 -1。
#数组#二分查找
解题主线
01
闭区间写法始终维护答案若存在则位于 [left, right]，循环条件必须是 left <= right。
解法 1：迭代二分
比较中点后排除不可能包含目标的一半闭区间。
时间复杂度
O(log n)
空间复杂度
O(1)
java
final class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle] == target) return middle;
if (nums[middle] < target) left = middle + 1;
else right = middle - 1;
}
return -1;
}
}比较中点后排除不可能包含目标的一半闭区间。
解法 2：递归二分
递归传递仍可能包含目标的闭区间，区间为空时失败。
时间复杂度
O(log n)
空间复杂度
O(log n)，递归栈
java
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;
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