Definition
Binary Search is a searching algorithm which can be used on the sorted array to reduce the time complexity from O(n) to O(log n) where n is the number of elements in an array.
It works by repeatedly dividing the search space in half until the target element is found or it is clear that the element is not present in the array.
It can be used to find the lower bound and upper bound in search space.
public static int findLowerBound(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if (array[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static int findUpperBound(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (array[mid] > target) {
high = mid - 1;
} else {
low = mid;
}
}
return low;
}
Binary Search can have two search spaces:
On Problem
https://leetcode.com/problems/find-smallest-letter-greater-than-target/On Answer
https://www.interviewbit.com/problems/square-root-of-integer/
So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.
Thank you, Have a nice day !!