二、经典算法之折半查找

很多同学对于二分法就是：一看就会，一写就废！！！！

易错点1：以下循环方式写哪一个？

方案一：while(left<right)
方案二：while(left<=right)

易错点2:如果arr[mid]<target,以下赋值该选哪一个(左半边同理)

方案一：right = mid;
方案二：right = mid - 1;

二、循环不变量

关于我们在while()循环当中所要搜素的数据我们将其分为以下四种

①:左闭右闭 [left,right]

体现在代码上就是

while(left<=right)

②:左闭右开 [left,right)

体现在代码上就是

while(left<right)

③:左开右闭 (left,right]

④:左开右开 (left,right)

后两种一般不做讨论，因为在实际的案例或者大型开源项目当中，所采用的的规则一般是前两种。
我们在while循环当中要坚持对区间的定义，这样才能更好的把控好易错点2当中所提出的问题，我们才能对边界做出一个理性的分析。而不是背写来…
同学们之所以会出现错误，最大原因在于没有坚持好 循环不变量这个原则，比如我们在while循环当中选择了左闭右闭，但是在操作过程当中却编程了左闭右开或者其他的什么…

三、左闭右闭 [left,right]的写法

重点解释：为什是是 right = mid -1; left=mid+1;

**举反例：**以下数据和目标值

如果我们采用的是 左闭右闭的写法，并且使用 left = mid 和 righ = mid;
第一轮：mid = 3:target<arr[mid];rigt指向mid的位置。
第二轮：mid = 0;target>arr[mid];left执行mid的位置。
第三轮：mid = 0;target>arr[mid];left执行mid的位置。
第四轮：mid = 0;target>arr[mid];left执行mid的位置。
......死循环

 public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while(left<=right){
            int mid = (left + right) / 2;
            if(nums[mid]<target){
                left = mid + 1;
            }else if(nums[mid]>target){
                right = mid - 1;
            }else if(nums[mid] == target){
                return mid;
            }else{
                return -1;
            }
        }   
        return -1;
}

四、左闭右开 [left,right)的写法

重点解释：为什是是 right = mid;和 left = mid+1;

举反例：

如果我们采用的是 左闭右开的写法，并且使用 left = mid+1 和 righ = mid - 1;
第一轮：left < right; mid = 3; target<nums[mid]; 则:right指向了数值0的位置.....
第二轮：left < right; mid = -1; target<nums[mid]; 则:right直接出界.....

 int left = 0;
 int right = nums.length; //定义右游标,这个地方要注意
 int mid = 0;
 while(left<right){
     mid = (left + right) / 2;
     if(nums[mid]<target){
         left = mid+1;
     }else if(nums[mid]>target){
         right = mid;
     }else if(nums[mid]==target){
         return mid;
     }else{
         return -1;
     }
}

总结

我们需要注意：
闭区间： 既然我们已将判断了arr[mid]<targrt或者arr[mid]>targrt，我们指针指向哪里哪里就是我们实际的索引区域，所以出现： left = mid + 1; right = mid-1;
开区间： 既然我们已将判断了arr[mid]<targrt或者arr[mid]>targrt，我们指针指向哪里哪里的下一位就是我们实际的索引区域，所以出现： left = mid; right = mid;