给定一个n个元素有序的(升序)整型数组 nums 和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回-1。
1、条件
-
查找的数量只能是一个,不能是多个;
-
用于查找的内容逻辑上是有序无重复的;
2、分类
根据查找的区间(中间数字到底该不该加入到下一次查找中),可分为1、左闭右闭;2、左闭右开;
3、思想
- 判断左右值和target大小规定左右索引范围;
- 循环条件一定要和区间分类一致,两种区间循环条件也不一致;
- 左闭右闭循环不加等号会出现找不到target;左闭右开循环加等号,当值在数组里没有时,跳不出循环并输出-1
4、代码
int search(vector<int>& nums; int target)
{
int left = 0;
int right = nums.size() - 1;
while (left <= right)
{
int middle = (left + right)/2;
if (nums[middle] < target)
{
left = middle + 1;
}
else if(nums[middle] > target)
{
right = middle - 1;
}
else
{
return middle;
}
}
return -1;
}
while(left <= right):这个小于等于一定要,不要最后一次循环时有可能找不到target;
int search(vector<int>& nums; int target)
{
int left = 0;
int right = nums.size() - 1;
while (left < right)
{
int middle = (left + right)/2;
if (nums[middle] < target)
{
left = middle + 1;
}
else if(nums[middle] > target)
{
right = middle;
}
else
{
return middle;
}
}
return -1;
}
while(left < right):等于一定不能要,会陷入死循环
left = middle + 1;需要+1,不然当搜索一个不属于数组的数字时,会陷入无限循环
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)