1. Introduction

Binary Search is an efficient algorithm for finding an item from a sorted array of items. It works by repeatedly dividing in half the portion of the array that could contain the item until you’ve narrowed down the possible locations to just one.

2. Program Steps

1. Initialize a sorted array.

2. Define the target value that we are searching for.

3. Define three pointers: low, high, and mid. Initialize low to the first index of the array and high to the last.

4. While low is less than or equal to high, calculate mid as the middle index of the current subarray.

5. Compare the middle element of the array with the target value.

6. Adjust the low and high pointers and repeat the search in the corresponding half of the array.

3. Code Program

public class BinarySearch {

    public static void main(String[] args) {
        // Step 1: Initialize a sorted array
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        // Step 2: Define the target value that we are searching for
        int target = 7;

        // Step 3: Define three pointers: low, high, and mid.
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            // Step 4: Calculate mid as the middle index of the current subarray
            int mid = low + (high - low) / 2;

            // Step 5: Compare the middle element of the array with the target value
            if (array[mid] == target) {
                System.out.println("Element found at index: " + mid);
                return;
            } else if (array[mid] < target) {
                // Adjust the low pointer
                low = mid + 1;
            } else {
                // Adjust the high pointer
                high = mid - 1;
            }
        }
        System.out.println("Element not found in the array.");
    }
}

Output:

Element found at index: 6

4. Step By Step Explanation

In Step 1, we initialize a sorted integer array.

For Step 2, we define the target value that we are searching for.

In Step 3, we initialize three pointers: low, high, and mid. low is set to the first index of the array, and high is set to the last.

During Step 4, within the while loop, we calculate mid as the middle index of the current subarray using the formula low + (high – low) / 2 to avoid overflow.

In Step 5, we compare the middle element of the array with the target value. Depending on the comparison, we adjust the low and high pointers and repeat the search in the corresponding half of the array until the target is found or the subarray has no elements.

Finally, we print the index at which the element was found or a message indicating that the element is not present in the array.