Binary Search in Arrays (Java)

What is Binary Search?

Binary search is a fast searching technique that works only on a sorted array.

Key Rule:

⚠️ Array must be sorted

How Binary Search Works:

1. Find middle element

2. Compare key with middle

3. If smaller → search left half

4. If larger → search right half

Algorithm:

1. Set low = 0, high = n−1

2. Find mid = (low + high) / 2

3. Compare key with arr[mid]

4. Repeat until found or range ends

Java Program:

class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int key = 40;

        int low = 0, high = arr.length - 1;
        boolean found = false;

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

            if (arr[mid] == key) {
                System.out.println("Element found at index " + mid);
                found = true;
                break;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (!found) {
            System.out.println("Element not found");
        }
    }
}

Time Complexity:

• Best Case: O(1)

• Worst Case: O(log n)

Advantages:

• Very fast

• Efficient for large data

Limitations:

• Requires sorted array

Linear Search vs Binary Search