Thinking process

search by index

there's a condition that half of the input satisfy and the other half doesn't

Mistakes

what if the case [1,2,3,4]

don't leave one case that neither left pointer nor right pointer doesn't move at all

public class Solution {
    //[3,4,5,1,2]
    //[1,2,3]
    public int findMin(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int l = 0;
        int r = nums.length - 1;

        while (l + 1 < r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] > nums[r]) {
                l = mid;
            } else {
                r = mid;
            } 
        }

        return nums[l] > nums[r] ? nums[r] : nums[l];

    }
}

Follow-up

what if duplicates are allowed?

LC 154

Mistakes

[3,3,1,3]

when nums[mid] equals to both nums[l] and nums[r], we can't decide whether the smallest is on the left or on the right. What we can do is simply move right pointer left by one OR move the left pointer right by one

public class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int l = 0;
        int r = nums.length - 1;

        while (l + 1 < r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] == nums[r] && nums[mid] == nums[l]) {
                r--;
            } else if (nums[mid] > nums[r]) {
                l = mid;
            } else {
                r = mid;
            } 
        }

        return nums[l] > nums[r] ? nums[r] : nums[l];

    }
}