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;
}
};