public static int search(int[] arr, int key) {
if(arr == null || arr.length == 0) {
return -1;
}
int pivotIdx = findPivotIdx(arr);
int res = find(arr, key, 0, pivotIdx);
if(res != -1) {
return res;
}
return find(arr, key, pivotIdx + 1, arr.length - 1);
}
private static int findPivotIdx(int[] arr) {
int left = 0;
int right = arr.length - 1;
int mid = right / 2;
while(left < mid) {
if(arr[left] < arr[mid]) {
left = mid;
}
else {
right = mid;
}
mid = left + (right - left) / 2;
}
return mid;
}
private static int find(int[] arr, int key, int start, int end) {
int left = start;
int right = end;
int mid = start + (end - start) / 2;
while(left <= right) {
if(key < arr[mid]) {
right = mid - 1;
}
else if(key > arr[mid]) {
left = mid + 1;
}
else {
return mid;
}
mid = left + (right - left) / 2;
}
return -1;
}
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5141325911425024