1. Search in Rotated Sorted Array

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.

public class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length - 1;

        while(left <= right) {

            int mid = (left + right) / 2;

            if(nums[mid] == target)
                return mid;

            else if(nums[left] <= nums[mid]) {
                if(nums[left] <= target && target < nums[mid])
                    right= mid - 1;
                else
                    left = mid + 1;
            }
            else {
                if(nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right= mid - 1;
            }
        }

        return -1;
    }
}

2. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order ofO(logn).

If the target is not found in the array, return[-1, -1].

For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].

public class Solution {
    public int[] searchRange(int[] nums, int target) {

        if(nums.length == 0) return new int[]{-1,-1};

        int left = 0, right = nums.length - 1, mid;
        while(left < right) {

            mid = (left + right) / 2;

            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }

        if(nums[left] != target) return new int[]{-1,-1};

        int[] ans = new int[2];
        ans[0] = left;

        right = nums.length - 1;

        while(left < right) {

            mid = (left + right) / 2 + 1;

            if(target < nums[mid])
                right = mid - 1;
            else
                left = mid;
        }

        ans[1] = left;
        return ans;
    }
}

3. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

public class Solution {
    public int searchInsert(int[] nums, int target) {

        if(nums.length == 0) return 0;
        if(nums[nums.length - 1] < target) return nums.length;

        int left = 0, right = nums.length - 1;
        while(left < right) {

            int mid = (left + right) / 2;

            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }

        return left;
    }
}

4. Search in Rotated Sorted Array II

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).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

public class Solution {
    public boolean search(int[] nums, int target) {

        if(nums.length == 0) return false;

        int left = 0;
        int right= nums.length - 1;

        while(left <= right){

            int mid = (left + right) / 2;
            if(nums[mid] == target)    
                return true;

            if(nums[mid] > nums[left]){
                if(nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else if (nums[mid] < nums[left]){
                if(nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right= mid - 1;
            }
            else
                left++;
        }

       return false;
    }
}

5 Find Minimum in Rotated Sorted Array

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).

Find the minimum element.

You may assume no duplicate exists in the array.public class Solution {
    public int findMin(int[] nums) {

        if(nums.length == 0) return 0;

        int left = 0;
        int right= nums.length - 1;

        while(left < right) {

            int mid = (left + right) / 2;

            if(nums[right] < nums[mid])
                left = mid + 1;
            else 
                right = mid;
        }

        return nums[left];
    }
}

6 Find Minimum in Rotated Sorted Array II

Follow upfor "Find Minimum in Rotated Sorted Array":
What ifduplicatesare allowed?

Would this affect the run-time complexity? How and why?

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).

Find the minimum element.

The array may contain duplicates.

public class Solution {
    public int findMin(int[] nums) {

        if(nums.length==0) return 0;

        int left = 0;
        int right= nums.length - 1;

        while(left<right){

            int mid = (left + right)/2;
            if(nums[mid] > nums[right])
                left = mid + 1;
            else if(nums[mid] < nums[right])
                right = mid;
            else 
                right--;
        }
        return nums[left];
    }
}