一.方法介绍

  1. 核心思想：以某种方式去掉一边，
  2. 对于原来有序，旋转一次后的数组，通过middle和right(或left)的值的比较，可以确定这个m是落在哪个部分。具体是用right还是left的值比较，则取决于哪个用二分法能筛掉一部分。

二分查找的关键点在于：

  1. 利用数组自身特点，想办法排除掉一边，缩减查找的总量
  2. 中间下标m的计算方式m=(l+r)/2
  3. 中间值nums[m]与目标值的比较，如果不等于，则会舍弃一半的区间不用比较，[l,r]的端点变动，端点右下标或者变成m-1，端点左下标或者变成m+1


二.Leetcode题

33.搜索旋转排序数组

题目链接
先判断哪边是有序的，（通过端点和中间值可以比较出来）
再看target在不在这个有序段里，在，排除无序的那段，不在的话，则排除有序的这段。

  1. 一个关键的点是对middle确定是哪一部分有序，通过nums[0]、nums[lens-1]这两个锚点和nums[middle]进行比较，并以此进行讨论
  2. 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环。

二分查找 - 图1 

  1. int search(vector<int>& nums, int target) {
  2.         int left=0,right=nums.size()-1,middle,lens=nums.size();
  3.         if (lens==1)
  4.             return (nums[0]==target)? 0:-1;
  5.         while (left<=right) {
  6.             middle=(left+right)/2;
  7.             if (nums[middle]==target)
  8.                 return middle;
  9.             if (nums[0]<=nums[middle]) { //middle左边是有序的
  10.                 if (nums[0]<=target&&target<nums[middle])
  11.                     right=middle-1;
  12.                 else
  13.                     left=middle+1;
  14.             }else {      //middle右边是有序的
  15.                 if (nums[middle]<target&&target<=nums[lens-1])
  16.                     left=middle+1;
  17.                 else
  18.                     right=middle-1;
  19.             }
  20.         }
  21.         return -1;
  22.     }

34.在排序数组中查找元素的第一个和最后一个位置

题目链接
给定一个按照升序排列的整数数组nums

自己构思的二分法查找：如果中间值等于目标值，则往中间值的左右去找， 如果中间值小于目标值，则舍弃左半区间，如果中间值大于目标值，则舍弃右半区间

69.x的平方根

题目链接

  1. 区间在[0,x]进行二分查找。
  2. 确定答案a的两种方法：一是满足a^2<=x且(a+1)^2>x；另一种是在二分时，保留最后满足middle^2<=x的那个middle.

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试 ans+1 了。

剑指Offer 11.旋转数组的最小数字

题目链接

  1. left，right，middle，利用最小值的右边都是不小于其的数的特点，将num[middle]和num[right]进行比较讨论。
  2. 当num[right]<num[middle]时，说明此时middle出现在最小值的左边了，可以舍弃左半区间的值，left=middle+1;
  3. 当num[right]>num[middle]时，说明此时middle是最小值或者是在最小值的右边，可以舍弃右边区间，此时，right=middle
  4. 当num[right]==num[middle]时，不能轻易舍弃某个区间，但是可以把num[right]这个值给舍弃掉，也即令right=right-1，以此缩小范围

  5. 最后结束循环时， num[left]即为最小值，或者num[right]

    1. int minArray(vector<int>& numbers) {
    2.      int left,right,middle,lens=numbers.size();
    3.      for (left=0,right=lens-1;left<right;) {
    4.          middle=(left+right)/2;
    5.          if (numbers[middle]>numbers[right]) {
    6.              left=middle+1;
    7.          }else if (numbers[middle]<numbers[right]) {
    8.              right=middle;
    9.          }else{
    10.              right-=1;
    11.          }
    12.      }
    13.      return numbers[left];
    14.  }

    剑指Offer 53. 0~n-1中缺失的数字

    题目链接

  6. i 表示的含义是 i 的左边都是正确位置的部分，j的右边是已经错位的部分，当i>j时，得到的i就是答案

  7. 二分查找，跳出循环时，i指向的是开始错位的第一个位置，j指向的是正确位置的末尾。
    1. int missingNumber(vector<int>& nums) {
    2.      int i,j,m;
    3.      for (i=0,j=nums.size()-1;i<=j;){
    4.          m=(i+j)/2;
    5.          if (nums[m]==m) 
    6.              i=m+1;
    7.          else
    8.              j=m-1;
    9.      }
    10.      return i;
    11.  }