33. Search in Rotated Sorted Array (Medium)

https://leetcode.com/problems/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,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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Hints

Solutions

https://www.cnblogs.com/springfor/p/3858140.html

class Solution {
    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;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-09 11:55:30

results matching ""

    No results matching ""