In this code, index of 0 (target) is not coming out to be -1, whereas of other numbers index ii coming out correctly. This is happening only with 0. What is the bug in this code?
public class binarySearch {
public static void main(String[] args) {
int[] arr = {-14, -5, 0, 3, 23, 49, 74, 106};
int target = 0;
int ans = answer(arr, target);
System.out.println(ans);
}
static int answer(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
boolean isAsc = arr[start] < arr[end];
while(start <= end) {
int mid = start + (end - start) / 2;
if(arr[mid] == target) {
return mid;
}
if(isAsc) {
if(mid < target) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
else {
if(mid < target) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return -1;
}
}
The problem in the code is when you compare the value is < target. But currently, you are comparing the index with the target which will not match and it behaves differently.
public static void main(String[] args) {
int[] arr = {-14, -5, 0, 3, 23, 49, 74, 106};
// int[] arr = {106, 74, 49, 23, 3, 0, -5, -14};
int target = 0;
int ans = answer(arr, target);
System.out.println(ans);
}
static int answer(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) {
return mid;
}
if (isAsc) {
if (arr[mid] < target) { // the fix
start = mid + 1;
} else {
end = mid - 1;
}
} else if (arr[mid] < target) { // the fix
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}