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.

C++:
01 bool search(int A[], int n, int target) {
02      int i=0;
03      int j=n1;
04      while(i<=j){
05          int mid=(i+j)/2;
06          if(A[mid]==target)
07               return true;
08          if(A[i]<A[mid]){
09               if((A[i]<=target)&&(target<A[mid]))
10                   j=mid1;
11               else
12                   i=mid+1;
13          }
14          else if(A[i]>A[mid]){
15               if((A[mid]<target)&&(target<=A[j]))
16                   i=mid+1;
17               else
18                   j=mid1;
19          }
20          else
21               i++;
22      }
23      return false;
24 }
Advertisements
This entry was posted in Array and linked list, Binary search. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s