Interview Question
Country: United States
This is my solution -
class SortedArrayElementPivot {
static int search(int[] array, int elementToSearch) {
if (array == null || array.length == 0) {
return -1;
}
return search(array, elementToSearch, 0, array.length - 1);
}
private static int search(int[] array, int elementToSearch, int start, int end) {
if (array == null || array.length == 0 || start < 0 || start > end || end > array.length - 1) {
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == elementToSearch) {
return mid;
}
if (
// mid is pivot
(mid > 0 && array[mid - 1] > array[mid])
// next to mid is pivot
|| (mid + 1 <= end) && array[mid] > array[mid + 1]) {
int leftSearchResult = binarySearch(array, elementToSearch, start, mid - 1);
return leftSearchResult != -1 ? leftSearchResult : binarySearch(array, elementToSearch, mid + 1, end);
} else {
int leftSearchResult = search(array, elementToSearch, start, mid - 1);
return leftSearchResult != -1 ? leftSearchResult : search(array, elementToSearch, mid + 1, end);
}
}
private static int binarySearch(int[] array, int elementToSearch, int start, int end) {
if (array == null || array.length == 0 || start < 0 || start > end || end > array.length - 1) {
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == elementToSearch) {
return mid;
} else if (array[mid] < elementToSearch) {
return binarySearch(array, elementToSearch, mid + 1, end);
} else {
return binarySearch(array, elementToSearch, start, mid - 1);
}
}
}
Here .
- NoOne June 13, 2019[ geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/ ]