4 Solutions Including Divide-and-Conquer, Binary Search (+ Follow-Up)
Solutions for 153 (no duplicate): link\n\nReference: LeetCode\nDifficulty: Hard\n\n## Problem\n\n> Suppose an array sorted in ascending order is rotated at some
Solutions for 153 (no duplicate): [link](https://www.junhaow.com/lc/problems/binary-search/rotated-sorted-array/153_find-minimum-in-rotated-sorted-array.html)\n\nReference: [LeetCode](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/)\nDifficulty: <span class="red">Hard</span>\n\n## Problem\n\n> Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.\n\n> (i.e., `[0,1,2,4,5,6,7]` might become  `[4,5,6,7,0,1,2]`).\n\n> Find the minimum element.\n\n> You may assume duplicate exists in the array.\n\n**Example:** \n\n```cpp\nInput: [3,4,5,1,2] \nOutput: 1\n\nInput: [2,2,2,0,1]\nOutput: 0\n\nInput: [3,3,3,3]\nOutput: 3\n\nInput: [3,6,3]\nOutput: 3\n\nInput: [3,1,3]\nOutput: 1\n```\n\n**Follow-up Questions:**\n\n- Would allow duplicates affect the run-time complexity? How and why?\n\n\n## Analysis\n\nSorting & Brute-Force as in 153.\n\n### Divide & Conquer\n\nReference: [Huahua](https://www.youtube.com/watch?v=P4r7mF1Jd50&list=PLLuMmzMTgVK5DkeNodml9CHCW4BGxpci7&index=11&t=0s)\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/lw8rc.png)\n\nIn the `mid3` case, the result could be calculated in `O(1)`.\n\n**Note:** Duplicates affect the run-time complexity. Consider the following case:\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/ogdgx.png)\n\n```cpp\npublic:\n  int findMin(vector<int>& nums)\n  {\n    return findMin(nums, 0, nums.size() - 1);\n  }\n\nprivate:\n  int findMin(const vector<int>& nums, int lo, int hi)\n  {\n    // only one element\n    if (lo == hi) \n      return nums[lo];\n\n    if (isSorted(nums, lo, hi)) \n      return nums[lo];\n    \n    int mid = lo + (hi - lo) / 2;\n    int left = findMin(nums, lo, mid);\n    int right = findMin(nums, mid + 1, hi);\n    return min(left, right);\n  }\n\n  bool isSorted(const vector<int>& nums, int lo, int hi)\n  {\n    return nums[lo] < nums[hi];  // must be < (<= will fail in the case [3, 1, 3])\n  }\n```\n\n**Time:** `O(\\log{N})`\n- False: `T(N) = 2T(N/2) = O(N)` \u274C\n  - At each level, at least one side could be done in `O(1)`.\n- True: `T(N) = O(1) + T(N/2) = O(\\log{N})`\n\n**Space:** `O(\\log{N})`\n\n\n\n### Binary Search\n\n\nThe basic idea is that if `nums[mid] >= nums[lo]` we assure that the inflection point is on the right part.\n\nHowever, unlike the solution in 153, we need 3 cases:\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/hd1z3.png)\n\nRecursion:\n\n```cpp\npublic:\n  int findMin(vector<int>& nums)\n  {\n    return findMin(nums, 0, nums.size() - 1);\n  }\n\nprivate:\n  int findMin(const vector<int>& nums, int lo, int hi)\n  {\n    // only one element\n    if (lo == hi) \n      return nums[lo];\n    \n    // the subarray is sorted\n    if (nums[lo] < nums[hi])\n      return nums[lo];\n    \n    int mid = lo + (hi - lo) / 2;\n\n    // changes here --> 3 cases\n    if (nums[mid] > nums[lo])\n    {\n      return findMin(nums, mid + 1, hi);\n    }\n    else if (nums[mid] < nums[lo])\n    {\n      return findMin(nums, lo, mid);\n    }\n    else  // nums[mid] == nums[lo]\n    {\n      return min(findMin(nums, mid + 1, hi), findMin(nums, lo, mid));\n    }\n  }\n```\n\nIteration:\n\nInvalid!\n\n```cpp\npublic:\n  int findMin(vector<int>& nums)\n  {\n    int lo = 0;\n    int hi = nums.size() - 1;\n    // stops when there is only one element\n    // in other words, it makes sure that there are at least 2 elements\n    while (lo < hi)\n    {\n      if (nums[lo] < nums[hi]) return nums[lo];\n      \n      int mid = lo + (hi - lo) / 2;\n      if (nums[mid] > nums[lo])\n      {\n        lo = mid + 1;\n      }\n      else if (nums[mid] > nums[lo])\n      {\n        hi = mid;\n      }\n      else\n      {\n        // ???\n      }\n    }\n    return nums[lo];\n  }\n```\n\n**Time:** `O(\\log{N})`\n- In the worst case scenario it would become `O(N)`.\n\n**Space:** `O(\\log{N})`\n\n\n
['Binary Search', 'Divide and Conquer', 'Recursion', 'C', 'Binary Tree', 'C++']