I used the similar approach with grokking solution but no need to findMax. So the runtime is a little bit less than the official solution. Can you help see which solution is better in coding interview? Thanks!
class SearchBitonicArray {
public static int search(int[] arr, int key) {
int start = 0, end = arr.length - 1;
if(arr[start] == key) return start;
if(arr[end] == key) return end;
while (start <= end){
int mid = start + (end - start) / 2;
if(arr[mid] < arr[mid + 1]){
// ascending
//compare the arr[mid] with key
if(arr[mid] < key){
start = mid + 1;
} else if (arr[mid] > key){
end = mid - 1;
} else {
return mid;
}
} else {
//descending
if(arr[mid] < key){
end = mid - 1;
} else if (arr[mid] > key){
start = mid + 1;
} else {
return mid;
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(SearchBitonicArray.search(new int[] { 1, 3, 8, 4, 3 }, 4));
System.out.println(SearchBitonicArray.search(new int[] { 3, 8, 3, 1 }, 8));
System.out.println(SearchBitonicArray.search(new int[] { 1, 3, 8, 12 }, 12));
System.out.println(SearchBitonicArray.search(new int[] { 10, 9, 8 }, 10));
System.out.println(SearchBitonicArray.search(new int[] { 0, 2, 4, 8,7, 6}, 7));
}
}
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5585107094077440
indent preformatted text by 4 spaces