Binary Search in Java for Competitive Programming

Introduction to Binary Search

Binary search is a highly efficient searching algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the middle element is the target value, the search is complete. If the target is less than the middle element, the search continues in the left half. If the target is greater, the search continues in the right half. This process is repeated until the target is found or the search interval is empty.

Applications of Binary Search: Searching in Sorted Arrays

The core application of binary search is efficiently finding elements within a sorted array. Its logarithmic time complexity (O(log n)) makes it significantly faster than linear search (O(n)) for large datasets.

Applying Binary Search to Solve Common Problems

Binary search is a versatile tool for solving various problems related to sorted arrays. Here are some common applications:

1. Finding an Element within a Range

This involves finding the first and last occurrences of a value in a sorted array, allowing you to determine the range where the value exists.

Java Solution:

 import java.util.Arrays;

class BinarySearchRange {

    // Function to find the first occurrence of a key in a sorted array
    public static int findFirst(int[] arr, int key) {
        int low = 0, high = arr.length - 1;
        int result = -1; // Initialize result to -1 (not found)

        while (low <= high) {
            int mid = low + (high - low) / 2; // Prevent integer overflow

            if (arr[mid] == key) {
                result = mid; // Potential first occurrence found
                high = mid - 1; // Continue searching on the left for an earlier occurrence
            } else if (arr[mid] < key) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
        return result;
    }

    // Function to find the last occurrence of a key in a sorted array
    public static int findLast(int[] arr, int key) {
        int low = 0, high = arr.length - 1;
        int result = -1; // Initialize result to -1 (not found)

        while (low <= high) {
            int mid = low + (high - low) / 2; // Prevent integer overflow

            if (arr[mid] == key) {
                result = mid; // Potential last occurrence found
                low = mid + 1; // Continue searching on the right for a later occurrence
            } else if (arr[mid] < key) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] arr = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
        int key = 5;

        int first = findFirst(arr, key);
        int last = findLast(arr, key);

        if (first != -1 && last != -1) {
            System.out.println("First occurrence of " + key + " is at index: " + first);
            System.out.println("Last occurrence of " + key + " is at index: " + last);
            System.out.println("Range of " + key + " is: [" + first + ", " + last + "]");
        } else {
            System.out.println(key + " not found in the array.");
        }

        key = 7;

        first = findFirst(arr, key);
        last = findLast(arr, key);

        if (first != -1 && last != -1) {
            System.out.println("First occurrence of " + key + " is at index: " + first);
            System.out.println("Last occurrence of " + key + " is at index: " + last);
            System.out.println("Range of " + key + " is: [" + first + ", " + last + "]");
        } else {
            System.out.println(key + " not found in the array.");
        }


        key = 9;

        first = findFirst(arr, key);
        last = findLast(arr, key);

        if (first != -1 && last != -1) {
            System.out.println("First occurrence of " + key + " is at index: " + first);
            System.out.println("Last occurrence of " + key + " is at index: " + last);
            System.out.println("Range of " + key + " is: [" + first + ", " + last + "]");
        } else {
            System.out.println(key + " not found in the array.");
        }

    }
} 

2. Determining the Presence of a Specific Value

The most basic application is checking whether a particular value exists in a sorted array.

Java Solution:

 import java.util.Arrays;

class BinarySearchPresence {
    public static boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevent integer overflow

            if (arr[mid] == target) {
                return true; // Target found
            } else if (arr[mid] < target) {
                left = mid + 1; // Search in the right half
            } else {
                right = mid - 1; // Search in the left half
            }
        }
        return false; // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 8, 11, 12};
        int target = 13;

        if (binarySearch(arr, target)) {
            System.out.println("Target " + target + " found in the array.");
        } else {
            System.out.println("Target " + target + " not found in the array.");
        }

        target = 8;

        if (binarySearch(arr, target)) {
            System.out.println("Target " + target + " found in the array.");
        } else {
            System.out.println("Target " + target + " not found in the array.");
        }
    }
} 

3. Finding the Floor and Ceiling of a Value

The *floor* of a value is the largest element in the array that is less than or equal to the value. The *ceiling* is the smallest element in the array that is greater than or equal to the value.

Java Solution:

 class FloorCeiling {

    public static int findFloor(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int floor = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return arr[mid]; // Target found, floor is the target itself
            } else if (arr[mid] < target) {
                floor = arr[mid];   //Update the floor value
                low = mid + 1;       //Move to search the right subarray for a bigger floor
            } else {
                high = mid - 1;      // Move to the left subarray because we seek a value less than the target
            }
        }
        return floor;  // return the floor value
    }

    public static int findCeiling(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int ceiling = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return arr[mid];  // Target found, ceiling is the target itself
            } else if (arr[mid] < target) {
                low = mid + 1;       // Move to the right subarray because we seek a value greater than the target
            } else {
                ceiling = arr[mid]; //Update the ceiling value
                high = mid - 1;      // Move to the left subarray for a smaller value for ceiling
            }
        }
        if(low < arr.length){
          return arr[low];
        }
        else{
          return -1;
        }


    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 8, 10, 10, 12, 19};
        int target = 5;

        int floor = findFloor(arr, target);
        int ceiling = findCeiling(arr, target);

        System.out.println("Floor of " + target + " is: " + floor);
        System.out.println("Ceiling of " + target + " is: " + ceiling);

        target = 20;
        floor = findFloor(arr, target);
        ceiling = findCeiling(arr, target);

        System.out.println("Floor of " + target + " is: " + floor);
        System.out.println("Ceiling of " + target + " is: " + ceiling);

        target = 0;
        floor = findFloor(arr, target);
        ceiling = findCeiling(arr, target);

        System.out.println("Floor of " + target + " is: " + floor);
        System.out.println("Ceiling of " + target + " is: " + ceiling);


    }
} 

4. Finding the Square Root of a Number

Binary search can be used to find the integer square root of a number. Since the potential square roots are in a sorted sequence (1, 2, 3,...), we can apply binary search.

Java Solution:

 class SqrtBinarySearch {

    public static int sqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

        int left = 1;
        int right = x;
        int ans = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // If mid*mid is equal to x
            if (mid <= x / mid) { // Use division to prevent overflow
                left = mid + 1;
                ans = mid;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int num = 16;
        System.out.println("Square root of " + num + " is: " + sqrt(num));

        num = 8;
        System.out.println("Square root of " + num + " is: " + sqrt(num));

        num = 25;
        System.out.println("Square root of " + num + " is: " + sqrt(num));

        num = 0;
        System.out.println("Square root of " + num + " is: " + sqrt(num));


        num = 1;
        System.out.println("Square root of " + num + " is: " + sqrt(num));

        num = 2147483647; //Max Int value

        System.out.println("Square root of " + num + " is: " + sqrt(num));
    }
} 

Conclusion

Binary search is a fundamental algorithm for competitive programming, offering efficient solutions to a wide range of searching and related problems on sorted data. Understanding and mastering its various applications is essential for success.