This is the vanilla binary search. We can use a no-brainer template. Here we will go over details and understand how this template was made. Oh and the brute force approach is just to scan the array and find the target.
While Loop
For any array question, we first check for the null/empty input. We want to set the base case as start and end next to each other. The merit of this approach is not very clear at this stage. But later we will see why this is very helpful. If the median < target, search the right section. If the median > target, search the left section. Solve the base case in the end.
public classicBS(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
Recursion
This might feel more natural to write but again recursion needs space on call stack to work. When the number is large enough, we might encounter stack overflow.
public int findPosition(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
return bsHelper(A, target, 0, A.length -1);
}
private int bsHelper(int[] A, int target, int start, int end) {
// base case
if (start + 1 >= end) {
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
// decrease
int mid = start + (end - start) / 2;
// conquer
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
// the median < target, search right section
// +/-1 since mid is not the target
return bsHelper(A, target, mid + 1, end);
} else {
// the median > target, search left section
return bsHelper(A, target, start, mid - 1);
}
}
Given a sorted array and a target, find the first occurrence of this target.
Now we see why we need to make our base case where start and end next to each other. For this question, we only have to change when A[mid] == target, end = mid.
Code
// first position of target
// don't return mid when == target, set end = mid
public firstPosition(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
Given a sorted array and a target, find the last occurrence of this target.
When A[mid] == target, start = mid. For the base case, check A[end] == target first.
Code
// last pos of target
// set start = mid, return end first after while loop
public firstPosition(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2; // notice write <= might get bug easily
if (A[mid] == target) {
start = mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[end] == target) {
return end;
} else if (A[start] == target) {
return start;
} else {
return -1;
}
}
Conclusion
The most transparent binary search question follows this format: We can check(A[index]) = {T, F}, then the array becomes [T, T, T, T, T, F, F, F, F, F]. We want to find the last T or the first F or in between.
