問題

定義局部最小的概念.

• arr長度為1時, arr[0]是局部最小
• arr長度為N(N > 1)時, 如果arr[0] < arr[1], 那么arr[0]是局部最小
• 如果arr[N-1] < arr[N-2]時, 那么arr[N-1]是局部最小
• 如果0 < i< N-1, 既有 arr[i] < arr[i - 1], 又有arr[i] < arr[i + 1], 那么arr[i]是局部最小
  給定一個無序數(shù)組arr, 已知arr中任意兩個相鄰的數(shù)都不相等. 寫一個函數(shù), 只需返回arr中任意一個局部最小出現(xiàn)的位置即可.

分析

順序遍歷是最直接的方法, 時間復雜度是O(n).
下面介紹一種時間復雜度O(logN)的方法.
基本思想: 二分查找.

1. 如果數(shù)組長度為0, 返回 -1
2. 如果數(shù)組長度為1, 返回0
3. 如果arr[0] < arr[1], 返回0
4. 如果arr[size - 1] < arr[size - 2], 返回size - 1
5. 從arr[1]到arr[size - 2]開始二分查找
6. left = 1, right = size - 2
7. mid = left + (right - left) / 2
8. 如果arr[mid] > arr[mid - 1], 那么在mid左側,必然存在局部最小位置, 令righ = mid - 1. 繼續(xù)二分查找
   舉個栗子: 對于數(shù)組 {x, 2, 3, 5, 6}, mid = 2, arr[2] > arr[1], 如果處于位置0的x值小于2, 那么滿足第三步的條件, 所以x值一定大于2, 位置1即是滿足條件的位置.
9. 同樣可以分析, 如果arr[mid] > arr[mid + 1], 那么在mid右側, 必然存在局部最小位置, 令left = mid + 1. 繼續(xù)二分查找.
10. 如果不滿足5.3, 5.4, 那么mid所在位置即是滿足條件的位置.

實現(xiàn)

class Solution                                                                                                                                        
{
public:
    int partialMinimum(const std::vector<int>& nums)
    {
        int size = nums.size();
        if (size == 0)
        {
            return -1;
        }
        if (size == 1 || nums[0] < nums[1])
        {
            return 0;
        }
        if (nums[size - 1] < nums[size - 2])
        {
            return size - 1;
        }
        int left = 1;
        int right = size - 2;
        int result = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid - 1])
            {   
                right = mid - 1;
            }   
            else if (nums[mid] > nums[mid + 1]) 
            {   
                left = mid + 1;
            }   
            else
            {   
                result = mid;
                break;
            }   
        }   
        return result;
    }
};