西樵网站设计制作,企业管理系统简称,宿迁房产网最新房价,网站开发qq群二分查找
题目描述
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。
示例 1:
输入: nums [-1,0,3,5,9,12], target 9…二分查找
题目描述
给定一个 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 t - 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(vectorint nums, int target) {// 初始化左、右双指针int left 0, right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(nums[mid] target) return mid;else if(nums[mid] target) left mid 1;else right mid - 1;}return -1;}
};朴素二分模板
while(left right){// 防止漏出int mid left (right - left) / 2;if(....) right mid - 1;else if(....) left mid 1;else return ......;}
