Using part of input array to compare numbers.
IntuitionUse part of input array to compare numbers.Solution Video⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️■ Subscribe URL
http://www.youtube.com/chann
# Intuition\nUse part of input array to compare numbers.\n\n# Solution Video\n\nhttps://youtu.be/JiNsSV16vLU\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 10,666\nThank you for your support!\n\n---\n\n# Approach\nThe description says "You must write an algorithm that runs in $$O(log n)$$ time.", so we will solve this question with `Binary Search`.\n\n```\nInput: nums = [3,4,5,1,2]\n```\nLet me put left, right and middle pointer.\n\n```\n[3,4,5,1,2]\n L   M   R\n```\nTypical Binary Search is like this.\n\n---\n\n\nIf a middle number is greater than a target number, we move `right` to `middle - 1`. On the other hand if the middle number is less than the target number, we will move `left` to `middle + 1`.\n\n**Binary search assumes that the input is sorted.**\n\n---\n\nThe target number for this question is a minimum number in the input, but problem here is that input array is rorated a few times.\n\n### How can we decide to move left or right pointer?\n\nIt\'s tough to think about whole array but part of array is still sorted in ascending order, even if the input is rotated.\n\nFor example,\n\n```\n[0,1,2,3,4,5]\n\u2193\n[4,5,0,1,2,3]\n```\nRotated twice. Between `4` and `5`, they are sorted and between `0` and `3`, they are also sorted. We will use those parts of array.\n\nLet\'s go back to main story.\n\nMy strategy is to compare middle number with right number. In this case, `5` and `2`.\n\n```\n[3,4,5,1,2]\n L   M   R\n```\n`5` is greater than `2`. That means we don\'t know how many numbers we have on the right side of the middle number, but we can say the numbers return to the minimum value and then begin to increase again on the right side of the middle number.\n\nTo prove that, let\'s think about this example quickly.\n\n```\n[1,2,3,4,5]\n L   M   R\n```\nIn this case, `3` is less than `5`. **That means minimum number is definitely on the left side of the middle number. That\'s because input array is sorted and the last number(= right number) is greater than middle number. We are sure that the numbers increase from middle to right.**\n\nLet\'s go back to main story again.\n\n```\n[3,4,5,1,2]\n L   M   R\n```\nMiddle number is greater than right number, so we can say at some point, the numbers return to minimum value. That\'s why we should move the left pointer to `middle pointer + 1`.\n\n```\n[3,4,5,1,2]\n     M L R\n```\n\nNext, middle pointer should be...\n\n```\n[3,4,5,1,2]\n       L R\n       M\n```\n\nCompare `1` with `2`. The `middle` number is less than the `right` number, so we are sure that the minimum number is on the left of the middle number.\n\nThere is one point when we move right pointer.\n\n---\n\n\u2B50\uFE0F Points\n\nWhen we move `right` pointer to left side, we will update `right` pointer with `middle pointer`. On the other hand when we move `left` pointer, we will update `left` pointer with `middle pointer + 1`.\n\nWhy? Let\'s think about this case.\n\n```\n[1,2,3,4,5]\n L   M   R\n```\nCompare `3` with `5`. We will move the `right` pointer to left side. In this case, we only know that the middle number is smaller than the right number, so **the middle number could still be the minimum value.** \n\n```\n[3,4,5,1,2]\n L   M   R\n```\n\nIn this case, since the middle number is greater than the right number, **it\u2019s impossible for the middle number to be the minimum value.** That\'s why we can update `left` pointer with `middle pointer + 1`.\n\n---\n\nLet\'s go back to main story again.\n\nIn this case, we will update `right` pointer with `middle` pointer.\n\n```\n[3,4,5,1,2]\n       L R\n       M\n\n\u2193\n\n[3,4,5,1,2]\n       L \n       M\n       R\n```\nNow `L == R`. We stop itertaion.\n\n```\nreturn 1(= left number or right number)\n```\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n\n---\n\n\n\n# Complexity\n- Time complexity: $$O(log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def findMin(self, nums: List[int]) -> int:\n    \n        left = 0\n        right = len(nums) - 1\n\n        while left < right:\n            mid = (left + right) // 2\n\n            if nums[mid] <= nums[right]:\n                right = mid\n            else:\n                left = mid + 1\n        \n        return nums[left]\n```\n```javascript []\nvar findMin = function(nums) {\n    let left = 0;\n    let right = nums.length - 1;\n\n    while (left < right) {\n        const mid = Math.floor((left + right) / 2);\n\n        if (nums[mid] <= nums[right]) {\n            right = mid;\n        } else {\n            left = mid + 1;\n        }\n    }\n\n    return nums[left];    \n};\n```\n```java []\nclass Solution {\n    public int findMin(int[] nums) {\n        int left = 0;\n        int right = nums.length - 1;\n\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n\n            if (nums[mid] <= nums[right]) {\n                right = mid;\n            } else {\n                left = mid + 1;\n            }\n        }\n\n        return nums[left];        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int findMin(vector<int>& nums) {\n        int left = 0;\n        int right = nums.size() - 1;\n\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n\n            if (nums[mid] <= nums[right]) {\n                right = mid;\n            } else {\n                left = mid + 1;\n            }\n        }\n\n        return nums[left];        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n1. **Initialize Pointers**\n\n   ```python\n   left = 0\n   right = len(nums) - 1\n   ```\n\n   - We define two pointers, `left` and `right`.\n   - `left` starts at the beginning of the array (`0`), and `right` starts at the last index (`len(nums) - 1`).\n   - The goal is to narrow down the range between `left` and `right` until we find the minimum element.\n\n2. **Binary Search Loop**\n\n   ```python\n   while left < right:\n   ```\n\n   - We enter a loop that continues as long as `left` is less than `right`.\n   - This loop performs a binary search to locate the minimum value in the rotated sorted array.\n\n3. **Calculate Midpoint**\n\n   ```python\n   mid = (left + right) // 2\n   ```\n\n   - We calculate the midpoint `mid` by taking the integer division of `(left + right) / 2`.\n   - `mid` represents the middle index of the current subarray defined by `left` and `right`.\n\n4. **Compare Midpoint with Right Element**\n\n   ```python\n   if nums[mid] <= nums[right]:\n       right = mid\n   ```\n\n   - If the element at `mid` is less than or equal to the element at `right`, this means the minimum element could be at `mid` or to its left (in the left half of the current subarray).\n   - We update `right` to `mid`, effectively discarding the right half of the array in the next iteration.\n\n5. **Move Left Pointer**\n\n   ```python\n   else:\n       left = mid + 1\n   ```\n\n   - If `nums[mid]` is greater than `nums[right]`, this means the minimum element must be in the right half of the current subarray.\n   - We update `left` to `mid + 1`, moving it to the right half of the array for the next iteration.\n\n6. **Return Minimum Element**\n\n   ```python\n   return nums[left]\n   ```\n\n   - Once the loop exits (when `left == right`), both `left` and `right` will be pointing to the minimum element in the array.\n   - We return `nums[left]` as the minimum value.\n\n\n---\n\nThank you for reading my post.\n\n##### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n##### \u2B50\uFE0F Related Video\n#33 Search in Rotated Sorted Array\n\nhttps://youtu.be/dO9OZJP_Hm8
['Array', 'Binary Search', 'C++', 'Java', 'Python3', 'JavaScript']