The binary search algorithm is an efficient method for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, it narrows the interval to the lower half; otherwise, it narrows it to the upper half. This process continues until the value is found or the interval is empty.

Java Program Implementation

/**
 * The BinarySearch class provides a method to perform binary search
 * on a sorted array of integers.
 */
public class BinarySearch {

    /**
     * Performs binary search on a sorted array to find the index of the target value.
     *
     * @param arr The sorted array of integers
     * @param target The value to search for
     * @return The index of the target if found; otherwise, -1
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

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

            // Check if the target is present at mid
            if (arr[mid] == target) {
                return mid; // Target found
            }

            // If target is greater, ignore left half
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }

        return -1; // Target not found
    }

    /**
     * Main method to test the binarySearch function.
     *
     * @param args Command line arguments
     */
    public static void main(String[] args) {
        int[] sortedArray = {2, 3, 4, 10, 40};
        int target = 10;
        
        int result = binarySearch(sortedArray, target);
        if (result == -1) {
            System.out.println("Element not found in the array");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Program Structure Explanation

• Class Definition: The class BinarySearch encapsulates the binary search functionality.
• Method binarySearch: This method takes a sorted array and a target value as parameters. It returns the index of the target if found or -1 if not found.
• Parameters:
  • arr: An array of sorted integers.
  • target: The integer value that we are searching for in the array.
• Variables:
  • left: The starting index of the search interval.
  • right: The ending index of the search interval.
  • mid: The middle index of the current search interval.
• While Loop: The loop continues as long as left is less than or equal to right. It calculates the middle index, compares it with the target, and narrows the search interval accordingly.
• Main Method: The main method initializes a sorted array and a target value, then calls the binarySearch method and prints the result.

Conclusion

The binary search algorithm is a powerful tool for efficiently searching sorted arrays. This implementation in Java demonstrates its core principles and structure, making it easy to adapt and utilize in various applications.