【二分查找】朴素二分查找
二分查找
题目描述
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 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]之间。
核心算法
朴素二分查找算法
- x left = mid + 1 [left, right]
- x > t -> right = mid - 1 [left, right]
- x == t 返回结果
细节问题
-
循环结束的条件
left > right
-
为什么是正确的?
二分查找算法之所以是正确的,是因为它利用了有序数组的性质,并通过不断缩小搜索范围的方式来快速定位目标元素。它的基本思想是将待搜索的数组分为两部分,然后通过比较目标值与中间元素的大小关系,确定目标值可能存在的区间,然后在该区间内继续二分查找,直到找到目标值或确定目标值不存在。
在每一次迭代中,二分查找算法将搜索区间缩小一半,因此它具有高效的搜索速度。由于每次都是将搜索区间减半,所以它的时间复杂度是O(log n),其中n是数组的长度。相比于线性搜索算法的时间复杂度O(n),二分查找算法在大规模数据集上具有更快的速度。
-
为什么时间快?
首先,二分查找算法每次将搜索区间缩小一半。假设待搜索的数组长度为n,在每次迭代中,查找区间的长度都会减半,因此经过k次迭代后,查找区间的长度将变为n/2^k。当查找区间的长度缩小到1时,就可以确定目标值的位置。所以,通过不断将搜索区间减半,二分查找算法能够在较少的比较操作中找到目标值,从而具有较快的时间复杂度。
其次,二分查找算法是基于有序数组进行查找。由于有序数组具有元素按照大小顺序排列的特点,可以利用这个特点进行二分查找。每次比较目标值与中间元素的大小关系,可以确定目标值在左半部分或右半部分,从而缩小搜索范围。这种有序性质使得二分查找算法能够更快地定位目标值,避免了无效的搜索。
class Solution { public: int search(vector& nums, int target) { // 初始化左、右双指针 int left = 0, right = nums.size() - 1; while(left int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if(nums[mid]
-