33.Search in Rotated Sorted Array (Medium) Facebook Microsoft Bloomberg Uber

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution 1: Binary Search O(log n); O(1)

    /**
     * Use 2 pointers from both left and right to find the target.
     The condition of while-loop is start + 1 < end
     Calculate the mid index.
     If nums’ mid == target, return mid.
     If nums’ mid > nums’ start (left)
     If target is between nums’ start and mid（which means target is in the ascending part）, 
     end = mid. Otherwise, target is in the descending part, start = mid.

     Otherwise, If target is between nums’ mid and end, start = mid. Otherwise, end = mid.
     Check if there is a number in the rest two numbers that is equal to target.
     If yes, return the corresponding index. Otherwise, return -1.
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > nums[start]) {
                if (nums[start] <= target && target <= nums[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }

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

Follow Up:

1. LC 81.Search in Rotated Sorted Array II

This problem is used to inspect if we can find the worst case, which is O(n). So we can just traverse the array to find the target. !!!But we can still use Binary Search to solve this problem.

   /**
     * Medium
     * O(log n) in average cases, but O(n) in worst cases, O(1)
     * This problem is used to inspect if we can find the worst case, e.g. [1, 1, 1, 1, 0], which is O(n).
     * So we can just traverse the array to find the target.
     * !!! But we can still use Binary Search to solve this problem.
     * We only need to add one more code line than the code of I.
     */
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > nums[start]) {
                if (nums[start] <= target && target <= nums[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else if (nums[mid] < nums[start]) {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                start++;    //the added code line
            }
        }
        if (nums[start] == target || nums[end] == target) {
            return true;
        }
        return false;
    }

    /**
     * O(n), O(1)
     */
    public boolean searchB(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }