🔍 What is Binary Search?

Binary Search is a search algorithm used to find the position of a target value in a sorted array. It repeatedly divides the search interval in half.

📌 Pre-condition:

• The array must be sorted (in ascending or descending order).

🧠 How It Works (Intuition)

Imagine you're guessing a number between 1 and 100. Each time, you ask if the number is higher or lower. You’re cutting the range in half — this is binary search in action.

✅ Basic Binary Search (Iterative)

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid overflow

        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // Not found
}

🔢 Example:

nums = [1, 3, 5, 7, 9], target = 5 → Output: 2

🧰 Step-by-Step Walkthrough

Input:

nums = [2, 4, 7, 10, 14, 19], target = 10

Steps:

1. left = 0, right = 5
2. mid = 2, nums[2] = 7 → 7 < 10 → move left = mid + 1 = 3
3. mid = 4, nums[4] = 14 → 14 > 10 → move right = mid - 1 = 3