ABOUT
只做题,想思路
二分法
思路:两端的平均数跟要找的值对比,小了就缩小左边区间,大了就缩小右边区间,然后再次求两端的平均数,小了就缩小左边区间,大了就缩小右边区间,最终到达循环结束
- 对比加缩小区间,写法很简单
if (nums[mid] > target){
right = mid;
}
else if (nums[mid] < target){
left = mid;
}
else if (target == nums[mid]){
return mid;
}
- 结束条件呢?
while(left <= right)
or
while(left < right)
- 假设第一种结束条件
while(left <= right) {//一定会存在一种情况就是左右区间取了相同值,这个区间是左闭右闭的
if (nums[mid] > target){
right = mid;
}
else if (nums[mid] < target){
left = mid;
}
else if (target == nums[mid]){
return mid;
}
mid = (left + right) / 2;
//考虑target在最右边,这个写法有问题
//考虑target在最左边,这个写法感觉没有什么问题,但是它循环了三次
}
当我们发现给left = mid;
改成left = mid + 1;
最右边的情况解决了,但是最左边的情况还是循环三次;那我们给它right = mid;
改成right = mid - 1;
循环次数少了一次
why?
你只要画一下图,你就会发现其实mid所指向的那个数根本没有比的必要,所以left = mid + 1;
可以,我刚刚说的target就算在最左边其实也可以比到,所以left可以加一
;
减一呢?是否是我上面说的减一是为了循环次数少了一次?NONONO,这个减一非常有必要的加上去,不然就会出现死循环,比如target是在0到1之间的数,left跟right最终只会等于1,而无法返回正确结果,虽然我们知道死循环就是无解,就应该返回-1。
所以代码的最终样子是这样的
class Solution {
public:
int search(vector<int>& nums, int target) {
if (0 == nums.size())
return -1;
int left = 0;
int right = nums.size() - 1;
int mid = (left + right) / 2;
if (nums[left] > target)
return -1;
if (nums[right] < target)
return -1;
if (nums[left] == target)
return left;
if (nums[right] == target)
return right;
//这四句是为了提高效率
while(left <= right){
if (nums[mid] > target){
right = mid - 1;
}
else if (nums[mid] < target){
left = mid + 1;
}
else if (target == nums[mid]){
return mid;
}
mid = (left + right) / 2;
}
return -1;
}
};
- 第二种呢?
while(left < right)
经过上面的思考,我们发现不会出现死循环了,因为left < right
,所以我们也不需要right = mid -1;
所以最终代码为:
class Solution {
public:
int search(vector<int>& nums, int target) {
if (0 == nums.size())
return -1;
int left = 0;
int right = nums.size() - 1;
int mid = (left + right) / 2;
if (nums[left] > target)
return -1;
if (nums[right] < target)
return -1;
if (nums[left] == target)
return left;
if (nums[right] == target)
return right;
while(left < right){
if (nums[mid] > target){
right = mid;
}
else if (nums[mid] < target){
left = mid + 1;
}
else if (target == nums[mid]){
return mid;
}
mid = (left + right) / 2;
}
return -1;
}
};