1. Introduction

Binary Search is a divide-and-conquer search algorithm that works on a sorted array or list. It finds the position of a target value by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half.

2. Program Steps

1. Initialize two pointers: low at position 0 and high at the last position of the array.

2. Calculate the middle index: mid = (low + high) / 2.

3. Compare the element at the middle index with the target value.

4. If they are equal, return the mid index.

5. If the target is larger than the middle element, update low to mid + 1 and repeat from step 2.

6. If the target is smaller than the middle element, update high to mid – 1 and repeat from step 2.

7. If the value isn’t present in the array, return -1.

3. Code Program

public class BinarySearch {

    // Binary search method
    static int binarySearch(int arr[], int x) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;

            // Check if x is present at mid
            if (arr[mid] == x)
                return mid;

            // If x is greater, ignore the left half
            if (arr[mid] < x)
                low = mid + 1;

            // If x is smaller, ignore the right half
            else
                high = mid - 1;
        }

        // if we reach here, then the element was not present
        return -1;
    }

    // Driver method
    public static void main(String args[]) {
        int arr[] = {2, 3, 4, 10, 40};
        int x = 10;
        int result = binarySearch(arr, x);
        if (result == -1)
            System.out.println("Element not present in the array");
        else
            System.out.println("Element found at index: " + result);
    }
}

Output:

Element found at index: 3

4. Step By Step Explanation

1. BinarySearch: This is the main class that contains methods for performing binary search on an array.

2. binarySearch(int arr[], int x): This is the method that implements the binary search algorithm. It takes in an array arr and a target value x to search for.

3. Within the binarySearch method, the middle index of the current search range is computed as mid = (low + high) / 2.

4. The element at mid is compared to the target x. If they match, mid is returned indicating the position of the target in the array.

5. If the target is greater than the middle element, the low pointer is moved one position past mid to search the right half.

6. If the target is less than the middle element, the high pointer is moved one position before mid to search the left half.

7. The search continues until low exceeds high or the target is found.

8. In the main method, an array is defined, the target value is set, and the binary search method is called. The result is then printed.

By dividing the search range in half with every step, Binary Search achieves a time complexity of O(log n), making it much faster than linear search for large datasets.