题解 | #旋转数组的最小数字#

这一题看过剑指offer有点印象，知道大致思路以及注意到的点

这里讲一下注意的点：

• 考虑数组本身就是有序递增的（中间索引初始化为左侧索引，循环条件为左侧元素大于右侧元素）
• 数组中有多个元素重复并且出现在两个子数组中（左中右三个索引元素相等时，只能使用迭代求最小）

代码不如官方简洁，还是不够精炼

class Solution {
  public:
    int minNumberInRotateArray(vector<int> rotateArray) {
      int left = 0, right = rotateArray.size() - 1;
        //  有序递增数组是第一个最小
      int mid = left;
      
        //  有序递增时不满足条件，跳过循环
      while (rotateArray[left] >= rotateArray[right]) {
        mid = left + ((right - left) >> 1);
        
          //  相邻时最小元素在第二个子数组
        if (right - left == 1) {
          mid = right;
          break;
        }
        
          //  三个元素值相等时，无法判断其在哪个子数组中
        if (rotateArray[left] == rotateArray[right] && rotateArray[right] == rotateArray[mid]) {
          return find_min(rotateArray, left, right);
        }
        
          //  left最后指向第一个子数组的最后一位
          //  right最终指向第二个子数组的首位，即最小元素
        if (rotateArray[mid] >= rotateArray[left]) {
          left = mid;
        } else if (rotateArray[mid] <= rotateArray[right]){
          right = mid;
        }
      }
      
      return rotateArray[mid];
    }
  private:
    int find_min(std::vector<int> &arr, int left, int right) {
      int min = arr[left];
      
      for (int i = left; i <= right; ++i) {
        if (arr[i] < min) {
          min = arr[i];
        }
      }
      
      return min;
    }
};