Binary Search
Binary search is one of the most important tools in algorithm. The questions related to it have different variations. The concept of binary search is easy too understand for most of people, but it will be quite annoying, when we are dealing with the indices. There are serveral ways to write the stopping conditions, for example:
- start < end
- start <= end
- start + 1 < end
- ...
and assign the middle index:
- start = mid
- start = mid +1
- end = mid + 1
- ...
If you didn't choose the correct way to manipulate the index, you may ended up with wrong solution or array index out of bound. To simplify the problem, the following is a universal template which could be adopted for any kind of binary search problems with only a minor modification.
//input: array of integers and a target, output: index of the location of target in array
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length = 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < target) {
start = mid;
} else if (nums[mid]> target) {
end = mid;
} else {
return mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
The key points which have to be noticed in above code are listed as follows:
- Stopping condition: start + 1 < end
- Calculate mid: start + (end - start) \/ 2
- Assign middle index: start = mid or end = mid
- Return nums[start] or nums[end] in the bottom of the code.
The algorithm stops when element start and element end are next to each other. Therefore, we have to check nums[start] and nums[end] _individually after stop. When we are calculating the mid, a different approach is applied which prevent overflow from (start + end). Since start and end are indicating different elements at any time, there is no need for _mid + 1.