704. 二分查找
查看题目简单
数组
二分查找
中频
解法一：二分查找
时间复杂度：O(log n) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 输入有序数组和目标值，然后点击开始
代码实现
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
时间复杂度：O(log n)
空间复杂度：O(1)
二分查找是一种在有序数组中查找特定元素的高效算法，其基本思想是将搜索区间不断减半，从而快速定位目标值。
### 算法步骤
1. 初始化搜索区间：左边界left=0，右边界right=nums.length-1
2. 当left <= right时，执行以下操作：
- 计算中间索引mid = (right - left) / 2 + left（避免整数溢出）
- 比较nums[mid]与目标值target
- 如果nums[mid] == target，返回mid（找到目标值）
- 如果nums[mid] > target，说明目标值在左半部分，更新right=mid-1
- 如果nums[mid] < target，说明目标值在右半部分，更新left=mid+1
3. 如果循环结束仍未找到目标值，返回-1
### 算法特点
- 时间复杂度：O(log n)，每次迭代将搜索区间减半
- 空间复杂度：O(1)，只使用常数个额外变量
- 仅适用于有序数组
- 是一种高效的查找算法，适用于大规模数据