一、题目介绍
给定一个 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]之间。
二、朴素二分查找
1. 核心原理
二段性 二分查找的前提是数据具有'二段性'。即对于有序数组,可以根据目标值将其划分为两个区间:左区间的元素均小于目标值,右区间的元素均大于目标值。每次只需判断中间元素与目标值的大小关系,即可安全地排除掉一半的搜索范围。
时间复杂度 O(log n)
由于每次比较后都能将搜索区间缩小一半,假设初始长度为 n,经过 x 次查找后区间长度变为 1,则有 n / 2^x = 1,解得 x = log₂n。因此时间复杂度为 O(log n)。
2. 通用模板
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止 left + right 溢出
if (nums[mid] < target) {
left = mid + 1;
} (nums[mid] > target) {
right = mid - ;
} {
mid;
}
}
-;


