class Solution {
public:
bool search(int A[], int n, int target) {
int low = 0 , high = n-1;
while( low <= high ) {
int mid = low + (high-low)/2;
if( A[mid] == target ) {
return true;
}
if( A[low] < A[mid] ) {
// left part is sorted
if( target >= A[low] && target < A[mid] ) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
else if( A[low] > A[mid] ) {
if( target > A[mid] && target <= A[high] ) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
else if( A[low] == A[mid] ) {
low++;
}
}
return false;
}
};
System Design for Beginners
A masterclass that helps early engineers and product managers become great at designing scalable systems.
180+ learners
Details →System Design Masterclass
A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.
1000+ learners
Details →Redis Internals
Learn internals of Redis by re-implementing some of the core features in Golang.
98+ learners
Details →