Find Minimum in Rotated Sorted Array, Find Minimum in Rotated Sorted Array II , Search in Rotated Sorted Array, Search in Rotated Sorted Array II, Search for a Range

Posted on 2015-09-10   |   In 刷题   |  

Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

  • If median element is larget than both low and high, then left part is increasing, smallest is in the right section
  • If median element is larger than low and smaller than high, then whole array is increaing, smallest is the left most item
  • If median element is smaller than both low and high, then the left part is increasing, smallest if in the left section
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int findMin(int[] nums) {
	int low=0, high=nums.length-1;
	while(low<high){
		int mid=(low+high)/2;
		if(nums[low]<=nums[mid] && nums[mid]<=nums[high]) return nums[low];
		else if(nums[mid]<=nums[low] && nums[mid]<=nums[high]){
			high=mid;
		}
		else if(nums[mid]>=nums[low] && nums[mid]>=nums[high]){
			low=mid+1;
		}
	}
	return nums[low];
}

Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.

Solution

  • If median equals to either low or high, move two pointers to the first non-duplicate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int findMin2(int[] nums) {
	int low=0, high=nums.length-1;
	while(low<high){
		int mid=(low+high)/2;
		while(nums[low]==nums[mid] && low<mid) low++;
		while(nums[high]==nums[mid] && high>mid) high--;
		if(nums[mid]>nums[high]){
			low=mid+1;
		}
		else{
			high=mid;
		}
	}
	return nums[low];
}

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 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.

O(Logn) Solution

  • Find min, then start from that index use binary search to find key, but this solution is LTE…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int search(int[] nums, int target) {
   	int low=0, high=nums.length-1, mid=0;
   	while(low<high){
   		mid=(low+high)/2;
   		while(nums[low]==nums[mid] && low<mid) low++;
   		while(nums[high]==nums[mid] && high>mid) high--;
   		if(nums[mid]>nums[high]){
   			low=mid+1;
   		}
   		else{
   			high=mid;
   		}
   	}
   	int min=low;
   	if(nums[nums.length-1]<target) {low=0;high=min-1;}
   	else {low=min; high=nums.length-1;}
       while(low <= high){
           mid = (low + high)/2;
           if(target < nums[mid]){
         	  high=mid-1;
           }
           else if(target > nums[mid]){
         	  low=mid+1;
           }
           else return mid;
       }
       return -1;	
   }

Solution

  • If target<mid, and mid<high, then right part is increasing, target is in [low,mid-1]
  • If target=high, then left part is increasing. If now target<low, then target is in [mid+1, high]; Else target is in [low, mid-1]
  • If target>mid, and mid>low, then left part is increasing, target is in [mid+1, high]
  • If target>mid, and mid<=low, then right part is increasing. If now target>high, then target is in [low, mid-1];
    Else target is in [mid+1, high]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int search(int [] A,int target){
       if(A==null||A.length==0)
         return -1;
        
       int low = 0;
       int high = A.length-1;
      
       while(low <= high){
           int mid = (low + high)/2;
           if(target < A[mid]){
               if(A[mid]<A[high])//right side is sorted
                 high = mid - 1;//target must in left side
               else
                 if(target<A[low])//target<A[mid]&&target<A[low]==>means,target cannot be in [low,mid] since this side is sorted
                    low = mid + 1;
                 else 
                    high = mid - 1;
           }else if(target > A[mid]){
               if(A[low]<A[mid])//left side is sorted
                 low = mid + 1;//target must in right side
               else
                 if(target>A[high])//right side is sorted. If target>A[high] means target is not in this side
                    high = mid - 1;
                 else
                    low = mid + 1;
           }else
             return mid;
       }
       
       return -1;
}

Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static boolean search(int [] A,int target){
        if(A==null||A.length==0)
          return false;
         
        int low = 0;
        int high = A.length-1;
       
        while(low <= high){
            int mid = (low + high)/2;
            if(target < A[mid]){
                if(A[mid]<A[high])//right side is sorted
                  high = mid - 1;//target must in left side
                else if(A[mid]==A[high]) high--; //move upper boundary
                else
                  if(target<A[low])//target<A[mid]&&target<A[low]==>means,target cannot be in [low,mid] since this side is sorted
                     low = mid + 1;
                  else 
                     high = mid - 1;
            }else if(target > A[mid]){
                if(A[low]<A[mid])//left side is sorted
                  low = mid + 1;//target must in right side
                else if(A[low]==A[mid]) low++; //move lower boundary
                else
                  if(target>A[high])//right side is sorted. If target>A[high] means target is not in this side
                     high = mid - 1;
                  else
                     low = mid + 1;
            }else
              return true;
        }
        
        return false;
 }

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
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].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] searchRange(int[] nums, int target) {
        int low=0, mid=0; 
        int high=nums.length-1;
        int[] result = new int[2];
     
        while(low<=high){
        	mid=(low+high)/2;
        	if(nums[mid]<target) low=mid+1;
        	else if(nums[mid]>target) high=mid-1;
        	else{
        		int l=mid, r=mid;
        		result[0]=mid; result[1]=mid;
        		while(l>=0 && nums[l]==target){			
        			result[0]=l;
        			l--;
        		}
        		
        		while(r<=nums.length-1 && nums[r]==target){
        			result[1]=r;
        			r++;
        		}
                return result;	
        	}
        }     
        return new int[]{-1,-1};
    }
#Array #Binary Search
Valid Parentheses, Longest Valid Parentheses, Generate Parentheses, Letter Combinations of a Phone Number, Restore IP Addresses, Valid Sudoku
Sudoku Solver, N-Queens, N-Queens II