2015年9月28日星期一

Leetcode 81 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: if nums[lo]=nums[hi], treat special, other part is same as problem I.
 public class Solution {  
   public boolean search(int[] nums, int target) {  
     int lo=0, hi=nums.length-1;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (nums[mid]==target) return true;  
       if (nums[lo]<nums[hi]) {  
         if (target>nums[mid]) lo=mid+1;  
         else hi=mid-1;  
       }  
       else if (nums[lo]>nums[hi]) {  
         if (nums[mid]>=nums[lo]) {  
           if (target<nums[mid] && target>nums[hi]) hi=mid-1;  
           else lo=mid+1;  
         }  
         else {  
           if (target>nums[mid] && target<nums[lo]) lo=mid+1;  
           else hi=mid-1;  
         }  
       }  
       else if (target==nums[lo]) return true;  
       else {  
         lo++;  
         hi--;  
       }  
     }  
     return false;  
   }  
 }  

没有评论:

发表评论