1.力扣刷题之二分查找

题目: 

思路

这道题首先要找出关键词:有序数组，元素不重复；这些都是使用二分法的前提条件，当我们看到这些字眼的时候，就要想一下是不是能用二分法。

二分法应该是我们刚学编程时最早遇到的算法题，思想很简单，代码也不困难，但是当中的边界问题，很容易出错。到底是while(left<right)还是while(left<=right)，到底是right=middle还是right=middle-1.我在前面有跟大家一起探讨过这类问题，感兴趣的可以看一下我这篇博客

写二分法，区间的定义主要是两种，左闭右闭即[left,right]或者左闭右开[left,right).

下面就跟大家一起用这两种写法来解题。

解题

左闭右闭

• while(left<=right):因为在左闭右闭[left,right]的区间内，所以left==right是有意义的，因此使用<=
• if(nums[middle]>target)right要赋值midd-1,因为当前这个nums[middle]一定不是要找的target并且middle右边的值都比这个目标值要大，所以接下来要缩小范围，那么接下来要查找的左区间结束下标位置就是middle-1

例如在数组，1,2,3,4,7,9,10中查找元素2，如图所示:

 代码示例:

class Solution {
public:
    int search(vector<int>& nums, int target) {
     int left=0;
     int right=nums.size()-1;//定义区间
     while(left<=right)
     {
         int mid=left+(right-left)/2;//防止溢出
         if(nums[mid]==target)
         {
             return mid;//找到target
         }
         else if(nums[mid]<target)
         {
             left=mid+1;//缩小区间,[mid+1,right]
         }
         else{
             right=mid-1;//缩小区间，[left,mid-1]
         }
     }
     return -1;//未找到目标值
    }
};

左闭右开

• while(left<right):因为区间是[left,right),所以left==right没有意义
• if(nums[middle]>target)right更新为middle,因为nums[middle]不等于target,并且middle右边的区间都比目标值大，要缩小区间，去左区间继续寻找，因为寻找的区间是左闭右开，所以right更新为middle,即下一个查询区间不会去比较nums[middle]

代码示例: 

class Solution {
public:
    int search(vector<int>& nums, int target) {
     int left=0;
     int right=nums.size();//定义区间
     while(left<right)
     {
         int mid=left+((right-left)>>2);//防止溢出
         if(nums[mid]==target)
         {
             return mid;//找到target
         }
         else if(nums[mid]<target)
         {
             left=mid+1;//缩小区间,[mid+1,right)
         }
         else{
             right=mid;//缩小区间，[left,mid-1)
         }
     }
     return -1;//未找到目标值
    }
};