Come and see! Binary search but logic is different, natural and intuitive
My Comment\nI see lots of posts solving this problem using binary search, but I cannot agree with their logic of binary search... Their logic is comparing the n
**My Comment**\nI see lots of posts solving this problem using binary search, but I **cannot agree with** their logic of binary search... Their logic is comparing the `num[mid]` with `nums[left/start]`, I would say **it is vague, and hard to understand...**\nI use binary search as well, but I always compare with `nums[n - 1]` which is easier. Please take a look at my logic and explanations\n\n---\n**Algorithm**\nBinary Search as you know\n\n---\n**Explanation**\nSince the original array is sorted in ascending order, `nums[0] < nums[n - 1]`\nIt would be like below:\n```\n\t\t /\t\n\t    /\n\t   /\n      /\n\t /\n    /\n   /\n```\nAfter rotated, think about how it would be like?\n```\n\t\t /\t\n\t    /\n<--\t   /\n      /\n------------------\n\t/\n   /\n  /\n\nIt becomes like below:\n  \n\t/\t\n   /\n  /\n /\n------------------\n\t\t/\n\t   /\n\t  / \n\n```\n\nWe can notice that from the pivot, **all the elements in the left hand side `>` all the elements in the right hand side**. And the largest number in the right hand side is `nums[n - 1]`\n\nWhen comes to binary search, 2 cases:\n1. If the `nums[mid]` is in the left hand side, look at the graph below, then it must be **greater than** the largest number in the right hand side, i.e. `nums[n - 1]`. That is **\'nums[mid] > nums[n - 1]\'**. Then we know the minimum number must in the right side of `mid`. So move `left` to `mid + 1`\n\t```\n\t   | /\t\n\t   |/\n\t   |\n\t  /|\n\t / |\n\t------------------\n\t\t\t/\n\t\t   /\n\t\t  / \n\t```\n2. If the `nums[mid]` is in the right hand side, look at the graph below, then it must be **no greater than** the largest number in the right hand side, i.e. `nums[n - 1]`. That is **\'nums[mid] <= nums[n - 1]\'**. Then we know the minimum number must in the left side of `mid`. So move `right` to `mid`. (Why `mid` not `mid - 1`? Because `num[mid]` can be the minimum number which is the result, we cannot rule out the `mid`)\n\t```\n\t\t/\t\n\t   /\n\t  /\n\t /\n\t------------------\n\t\t   | /\n\t\t   |/\n\t\t   |\n\t\t  /| \n\t```\n\nSo the difference with other solutions is: **we always compares the `nums[mid]` with `nums[n - 1]`.** Unlike other solutions comparing `nums[mid]` with `nums[left]` or `nums[right]`, the logic is vague, right???\n\n---\n**Final Code**\n```java\nclass Solution {\n    public int findMin(int[] nums) {\n        // corner case\n        if(nums == null || nums.length == 0) return -1;\n        if(nums.length == 1) return nums[0];\n        \n        // if the array is not rotated\n        int n = nums.length;\n        if(nums[0] < nums[n - 1]) return nums[0];\n        \n        // get to business: find min if array is rotated\n        int left = 0;\n        int right = n - 1;\n        while(left < right - 1){\n            int mid = left + (right - left)/2;\n            if(nums[mid] <= nums[n - 1]){\n                right = mid;\n            }else{\n                left = mid + 1;\n            }\n        }\n        \n        return Math.min(nums[left], nums[right]);\n    }\n}\n```\n\n---\n**Complexity Analysis**\nTC(Time Complexity): O(logn), since we are using binary search\nSC(Space Complexity): O(1)\n
['Binary Search', 'Java']