Javascript Solution using Binary Search in O(logn) time (w/ explanation)
Explanation\nMy solution for this problem utilises Binary Search. The reason I chose binary search was that the question mentioned that the solution has to have
## Explanation\nMy solution for this problem utilises **Binary Search**. The reason I chose binary search was that the question mentioned that the solution has to have a time complexity of O(logn). The naive method of iterating through the array and updating a variable to keep track of the minimum would be linear, O(n). Since binary search is known to have a time complexity of O(logn) I decided to go down that route.\n\nBut how do we use binary search for this problem? Here are the brief steps to my solution:\n\n1. Left and right are 2 pointers that keep track of the start and end of the subarray that we are currently searching.\n\n2. Within the loop, a mid pointer is calculated to be half the sum of left and right. We then start to compare the value at the mid pointer and the value at the right pointer. From here, there can only be 2 case:\n\n\t(a) nums[mid] > nums[right]\n\tFor an un-rotated sorted array, we can easily understand that there can never be a case where nums[mid] would ever be greater than nums[right]. However, this condition can happen in a rotated array if the mid pointer is residing on the left side of the rotated array. Once we know that the mid pointer is at the left side of the array, we can start to cut down our search to only the right side since we know that the minimum value can never be in the left side. Hence, we update the left pointer to be mid + 1, indicating that we are now searching the right side.\n\t\n\t(b) nums[mid] <= nums[right]\n\tThis condition will tell us that the subarray that we are currently searching is now a properly sorted array which is un-rotated. To get the minimum value of this subarray, we simply have to keep adjusting the right pointer to the left by setting the mid pointer as the right pointer, cutting down our serach to only the left half of this subarray. Eventually, we will reach the left most element of this subarray.\n\t\n\t***Note:*\n\t*For a sorted array of [4,5,6,7,0,1,2], the left side refers to the portion of the array on the left of the minimum value [4,5,6,7] and the right side refers to the portion of the array from the minimum value onwards [0,1,2].***\n\t\n3. Lastly, the while loop only ceases once the search is complete (the right and left pointer passes each other). At this point, the answer that we want will lie in nums[left].\n\t\n## Performance\n\nThe time complexity of this solution is, **O(logn)**, since at every stage of binary search, we are splitting the array into half.\n\nHere are the details of my submission:\nRuntime: 80 ms, faster than 42.33% \nMemory Usage: 39.2 MB, less than 29.36% \n\n## Code\n\n```\nvar findMin = function(nums) {\n    var left = 0,\n        right = nums.length - 1\n    \n    while (left < right){\n        var mid = Math.floor((left + right)/2)\n        if (nums[mid] > nums[right]) left = mid + 1\n        else right = mid\n    }\n    return nums[left]\n};\n```\n\nI hope this helps! Do let me know if there are any lapses in my explanation and/or if my solution can be improved in any way :)
['Binary Tree', 'JavaScript']