Binary search algorithm is a widely used algorithm for sorted sequences. It can be utilized not only for searching, but also for sorting and proving hypotheses on ranges.
The idea of the algorithm is quite simple:
- divide the range equally into 2 parts
- only the potential part of the range will be used for further processing.
For example, if we want to find some value in a sorted array:
– we divide the array into 2 equal parts
– we continue searching in potential parts that may contain the searchable value, and skip the other part.
Binary search algorithm is quite fast. Is time complexity is O(log n).
public class ImplementBinarySearch {
public static void main(String[] args) {
var sortedArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 19};
var searchItem = 4;
System.out.println(binarySearch(sortedArray, searchItem));
}
private static Integer binarySearch(int[] sortedArray, int searchItem) {
var low = 0;
var high = sortedArray.length;
var mid = (high + low) / 2;
while (low <= high && sortedArray[mid] != searchItem) {
if (searchItem > sortedArray[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
mid = (high + low) / 2;
}
if (sortedArray[mid] == searchItem) {
return mid;
} else {
return null;
}
}
}