二分查找(一)
一、简单二分查找
给定一个 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]
之间。
实现
class Solution {
public:
int search(vector<int>& nums, int target)
{
int n=nums.size();
int left=0,right=nums.size()-1,mid=0;
while(left<=right)
{
mid=left+(right-left+1)/2;//防止溢出
if(nums[mid]>target) right=mid-1;
else if(nums[mid]<target) left=mid+1;
else return mid;
}
return -1;
}
};
二、在排序数组中查找元素的第一和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10]
, target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10]
, target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
代码实现
判断循环的条件是left<right,因为如果target存在那么当left==right时,必然是相等的,又因为需要找出区间,所以需要分两次分别找出其左右端点,所以找左端点时,只要中间数>=target right指针就往mid移直到移动到最左边的target,而只要mid中间数<target,left就往mid+1移,而right如果先移动到最左边的三之后的操作right就不会再进行移动,如果时left先移动到最左边的target那么left就不会移动,所以当left==right时,只要数组中有target存在,那么当前下标绝对就是target。
接下来需要思考mid的计算问题,如果数组元素个数是奇数个,那每次都可以恰好找到中点,如果是偶数个,那就需要在中间两个元素中二选一,如果最后只剩left right,如果mid=left+(right-left+1)/2 而此时right所指向的正好是target那么程序就会陷入死循环,right会原地不动,而left则一直无法移动,所以,此时mid的计算方式就不能进行+1操作。
同理当最后个数为偶数个的时候,因为求得的mid会在left位置,此时left判断条件为如果小于等于就等于mid,如此以往,程序就会进入死循环。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ret;
if(nums.size()==0) return {-1,-1};
int n=nums.size()-1;
int left=0,right=0,mid=0;
for(left=0,right=n,mid=0;left<right;mid=left+(right-left)/2)//找左端点
{
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]!=target) return {-1,-1};//判断是否存在target
ret.push_back(left);
for(left=0,right=n,mid=0;left<right;mid=left+(right-left+1)/2)//找右端点
{
if(nums[mid]<=target) left=mid;
else right=mid-1;
}
if(nums[left]!=target) return {-1,-1};//判断是否存在target
ret.push_back(right);
return ret;
}
};
模板
原文地址:https://blog.csdn.net/2201_75880188/article/details/136380688
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!