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 class Solution {
02 public:
03     bool search(int A[], int n, int target) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int p=0;
07         int q=n1;
08         while(p<=q)
09         {
10             int t=p+(qp)/2;
11             if(A[p]==target)
12                 return true;
13             if(A[t]==target)
14                 return true;
15             if(A[q]==target)
16                 return true;
17             if(A[p]<A[t])
18             {
19                 if((target>A[p])&&(target<A[t]))
20                     q=t1;
21                 else
22                     p=t+1;
23             }
24             else if(A[p]>A[t])
25             {
26                 if((target>A[t])&&(target<A[q]))
27                     p=t+1;
28                 else
29                     q=t1;
30             }
31             else
32             {
33                 p++;
34                 q;
35             }
36         }
37         return false;
38     }
39 };
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