Binary Search Algorithm in Java

1. Introduction

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed the possibilities down to just one.

2. Implementation Steps

1. Start with the middle of the sorted list.

2. If the middle item matches the target value, return its index.

3. If the target value is less than the middle item, continue the search in the lower half of the list.

4. If the target value is greater than the middle item, continue the search in the upper half of the list.

5. Repeat steps 1-4 until the target value is found or the search interval is empty.

3. Implementation in Java

public class BinarySearch {
    // Binary Search method
    public static int binarySearch(int arr[], int l, int r, int x) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // Check if x is present at mid
            if (arr[mid] == x) {
                return mid;
            }
            // If x is greater, ignore left half
            if (arr[mid] < x) {
                l = mid + 1;
            }
            // If x is smaller, ignore right half
            else {
                r = mid - 1;
            }
        }
        // x was not found in the array
        return -1;
    }
    public static void main(String[] args) {
        int arr[] = { 1, 3, 5, 7, 9, 11, 13, 15 };
        int x = 9;
        int result = binarySearch(arr, 0, arr.length - 1, x);
        if (result == -1) {
            System.out.println("Element not present in the array");
        } else {
            System.out.println("Element is present at index: " + result);
        }
    }
}

Output:

Element is present at index: 4

Explanation:

1. Begin by examining the middle item of the sorted array.

2. If this item matches the target value, then the position of this item in the array is returned.

3. If the target value is less than this item, search for the item in the lower half of the array.

4. If the target value is greater than this item, search for the item in the upper half of the array.

5. Continue the process until the target item is found or the search interval is empty. If the interval becomes empty, return -1 to indicate the target value is not present in the array.