Binary Search

Binary Search

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:

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 !!