剑指offer_11_旋转数组中的最小数字

• 2019 年 10 月 6 日
• 筆記

如：{1,2,3,4,5}的一个旋转数组为{3,4,5,1,2} 该数组的最小值为1

初看题目我们最直观的解法并不难，遍历数组用俩个"指针"一前以后，当前面"指针"指向的元素比后面的"指针"指向的数组元素小时，这时我们就找到旋转数组中的最小元素，我们不难写出如下代码：

public static int findMin(int[] arr) {      // 如果数组是只有一个元素 则不是旋转数组同时也防止下边的i+1越界      if(arr == null || arr.length <= 1){          return -1;      }        for (int i =0 ; i < arr.length -1; i++) {          if (arr[i] > arr[i + 1]) {              return arr[i + 1];          }      }      return -1;  }

但是上面这种方法当数组的元素特别多时，效率是比较低的，不足以拿到offer，现在考虑用二分法对上面算法进行改良：

定义一个数组最左边的"指针"left和一个数组最右边的"指针"right，每次求俩个指针的中间值记为middle，如果left所对应的值要比middle小，那么说明数组还在递增中，最小值会在middle和right之间，这时候我们让left等于middle，继续用同样的方式缩小范围，如果middle要比right小，那么说明最小值在left和middle之间，让right等于middle，用同样的方式继续求下去，就能求到最小值啦。

public static int findMin(int []arr) {      int left = 0;      int right = arr.length;      while(left < right) {          int middle = (left + right) / 2;          if (arr[left] < arr[middle]) {              left = middle;          // 如果遇到相同的元素 我们就只能用遍历了          } else if(arr[left] == arr[middle]){              for(int i = left; i <= middle; i++) {                  if(arr[i] < arr[middle]) {                      return arr[i];                  }              }              return arr[left];          } else{              right = middle;          }          if (right - left == 1) {              if(arr[right] > arr[left])                  return arr[left];              else                  return arr[right];          }      }      return  arr[left];  }

当left对应的元素与right对应的元素相等时，这是特殊情况，这里选择遍历去找最小值。