Search in Rotated Sorted Array

Solution 1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int start = 0;
        int end = nums.size() - 1;

        while ( start <= end) {
            int mid = start + (end - start)/2;
            if (nums[mid] == target) return mid;

            // bug: if ( nums[start] < nums[mid] )
            if ( nums[start] <= nums[mid]) {
                    if (nums[start] <= target && nums[mid] > target) end = mid - 1;
                    else start = mid + 1;

            // nums[start] > nums[mid]
            } else {
                    if (nums[end] >= target && nums[mid] < target) start = mid + 1;
                    else end = mid - 1;
            }            
        }
        return -1;
    }
};

bug input: Time Limit Exceeded

[4,5,6,7,0,1,2]
3

Solution 2

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        int start = 0;
        int end = nums.size() - 1;

        while ( start + 1 < end) {
            int mid = start + (end - start)/2;
            if (nums[mid] == target) return mid;

            if ( nums[start] < nums[mid]) {
                // nums[mid] > target   also works, since we check equal in front
                if (nums[start] <= target && nums[mid] >= target) end = mid;
                else start = mid;

            } else if (nums[mid] < nums[end]) {
                if (nums[end] >= target && nums[mid] <= target) start = mid;
                else end = mid;
            }
        }

        if (nums[start] == target) return start;
        if (nums[end] == target) return end;
        return -1;    
    }
};

Search in Rotated Sorted Array || (Duplicate elements)

Corner cases

[1, 1, 1, 1, 0, 1, 1] 
[1, 1, 1, 3, 1, 1]

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if (nums.empty()) return false;
        int start = 0;
        int end = nums.size() - 1;

        while ( start <= end) {
            int mid = start + (end - start)/2;
            if (nums[mid] == target) return true;

            if ( nums[start] < nums[mid]) {
                    if (nums[start] <= target && nums[mid] >= target) end = mid - 1;
                    else start = mid + 1;
            // different with no duplicate elements
            } else if (nums[mid] < nums[start]) {
                    if (nums[end] >= target && nums[mid] <= target) start = mid + 1;
                    else end = mid - 1;
            } else {
                // [1, 1, 1, 1, 0, 1, 1] 
                // [start] = [mid] = [end]
                // if start move right by 1, mid will move right by 1 : mid = start + (end-start)/2;
                start++;
            }          
        }
        return false;
    }
};

left bottom case 1, right bottom case 2, right up case 3

Case 1: mid will move up, then different with [start] and [end]

Case 2: start will move up, then different with [mid] and [end]