二分查找（一）：朴素二分

一、题目介绍

704. 二分查找 - 力扣（LeetCode）

给定一个 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

提示：

1. 假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000] 之间。
3. 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; 
    }
}
 -;