数据结构与算法（查找和排序） --javascript语言描述

旋转数组的最小数字（二分查找）

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：

1.设置两个指针，初始状态第一个指针指向前面子数组的第一个元素，第二个指针指向后面子数组的最后一个元素；

2.找到两个指针的中间元素；

3.若其大于等于第一个指针指向的元素，则说明其在前面的子数组中，且显然最小元素在中间元素的右边，若其小于等于第二个指针指向的元素，则说明其在后面的子数组中，且显然最小元素在中间元素的左边。

如此，便可以缩小搜索范围，提高时间复杂度，最终第一个指针指向前面子数组的最后一个元素，而第二个指针指向后面子数组的第一个元素，它们处于相邻位置，而第二个指针指向的刚好是最小的元素。

注意：按旋转规则，第一个元素应该是大于或等于最后一个元素的；但也有特例：若把排序数组的前0个元素搬到最后面，及排序数组本身，仍是数组的一个旋转，此时数组中的第一个数字是最小的数字。

注意：当两个指针指向的数字及它们中间的数字三者相等时，无法判断中间数字位于前面的子数组还是后面的子数组，也就无法移动两个指针来缩小查找的范围，此时只能用顺序查找的方法。

例如：数组{1,0,1,1,1}和数组{1,1,1,0,1}都可看成是递增数组{0,1,1,1,1}的旋转。第一种情况，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。

function minNumberInRotateArray(arr) {
  let index1 = 0;
  let index2 = arr.length - 1;
  let indexMid = index1;
  while(arr[index1] >= arr[index2]) {
    if(index2 - index1 == 1) {
      indexMid = index2;
      break;
    }
    indexMid = Math.floor((index1 + index2 ) / 2);
    //如果下标为index1、index2和indexMid指向的三个数字相等
    //则只能顺序查找
    if(arr[index1] == arr[index2] && arr[indexMid] == arr[index1]) {
      return MininOrder(arr,index1,index2);
    }
    if(arr[indexMid] >= arr[index1]) {
      index1 = indexMid;
    }
    if(arr[indexMid] <= arr[index2]) {
      index2 = indexMid;
    }
  }
  return arr[indexMid];
}

//按顺序查找函数
function MininOrder(arr,index1,index2) {
  let res = arr[index1];
  for (var i = index1 + 1; i <= index2; i++) {
    if(res > arr[i]) {
      res = arr[i];
    }
  }
  return res;
}

console.log(minNumberInRotateArray([3,4,5,1,2]));