Binary Search — Searching

💡 What Is Binary Search?

Binary Search is a fast searching technique that works on sorted data.
Instead of checking every element one by one (like in linear search), it keeps dividing the list into halves and focuses only on the half that could possibly contain the element.

Because of this “divide and conquer” idea, Binary Search saves a lot of time — especially when dealing with large datasets.

⚙️ How It Works (Step by Step)

Let’s take an example.
Suppose we have a sorted array:

[5, 10, 15, 20, 25, 30, 35, 40]

and we want to find 25.

🪜 Step 1:

Find the middle element.

Start index = 0
End index = 7
Middle index = (0 + 7) / 2 = 3
Middle element = 20

Now compare 25 with 20.

25 is greater, so our target must be on the right half.

We can safely ignore the left half [5, 10, 15, 20].

🪜 Step 2:

Now look at the right half [25, 30, 35, 40].

Start index = 4
End index = 7
Middle index = (4 + 7) / 2 = 5
Middle element = 30

Compare again:

25 is smaller than 30, so we ignore everything on the right (30, 35, 40).

🪜 Step 3:

We now look at [25].

Start = 4
End = 4
Middle = 4
Middle element = 25

Perfect! ✅ We found our target.

🧠 Why “Binary”?

The word binary means “two.”
At every step, Binary Search splits the list into two parts and works with one part — either left or right.
That’s why it’s called Binary Search.

📈 Binary Search Diagram

Array: [5, 10, 15, 20, 25, 30, 35, 40]
Target: 25

Step 1 → [5, 10, 15, 20, 25, 30, 35, 40]
              ↑
            mid = 20 (Target > mid → search right half)

Step 2 → [25, 30, 35, 40]
              ↑
            mid = 30 (Target < mid → search left half)

Step 3 → [25]
              ↑
            mid = 25 (Found!)

🧩 Real-Life Analogy

Think of finding a friend’s name in your phone contacts (sorted alphabetically).
You don’t scroll one by one — you jump to somewhere in the middle, check if you’ve gone too far or not, and then adjust.
That’s exactly what Binary Search does — it jumps smartly instead of searching blindly.

💻 Simple Pseudocode

binarySearch(array, key):
    start = 0
    end = length(array) - 1

    while start <= end:
        mid = (start + end) / 2
        if array[mid] == key:
            return mid
        else if key < array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1

⏱️ Time Complexity

Best case: O(1) → if the element is found in the first comparison.
Average/Worst case: O(log₂ n) → because we keep cutting the search space in half each time.

That’s much faster than linear search, which takes O(n) time.