Binary Search

Binary search is an efficient searching algorithm that works on sorted data. Instead of checking every element one by one, it repeatedly divides the search area in half, quickly narrowing down the location of the target value.

---

Prerequisite: The Data Must Be Sorted

Binary search only works on sorted data (either ascending or descending order). If the data is unsorted, you must sort it first before applying binary search, or use linear search instead.

---

How Binary Search Works

1. Find the middle element of the list.
2. Compare the middle element with the target value.
3. If the middle element equals the target, the search is complete — return its position.
4. If the target is less than the middle element, discard the right half and repeat on the left half.
5. If the target is greater than the middle element, discard the left half and repeat on the right half.
6. Repeat until the target is found or the search area is empty (the target is not in the list).

The divide-and-conquer flow:

graph TD
    A["Start: low = 0, high = n - 1"] --> B{"low less than or equal to high?"}
    B -->|No| C["Return -1 (not found)"]
    B -->|Yes| D["mid = (low + high) DIV 2"]
    D --> E{"list[mid] = target?"}
    E -->|Yes| F["Return mid (found)"]
    E -->|No| G{"list[mid] < target?"}
    G -->|Yes| H["low = mid + 1 (search right half)"]
    G -->|No| I["high = mid - 1 (search left half)"]
    H --> B
    I --> B

---

Pseudocode for Binary Search

FUNCTION binarySearch(list, target)
    low = 0
    high = LENGTH(list) - 1
    WHILE low <= high
        mid = (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low = mid + 1
        ELSE
            high = mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Note: DIV means integer division (divide and round down). For example, 7 DIV 2 = 3.

---

Worked Example

Consider the sorted list: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Target: 23

Step	low	high	mid	list[mid]	Action
1	0	9	4	16	23 > 16, so low = 5
2	5	9	7	56	23 < 56, so high = 6
3	5	6	5	23	Found at index 5

Only 3 comparisons were needed for a list of 10 items. A linear search could have taken up to 10.

Target: 10

Step	low	high	mid	list[mid]	Action
1	0	9	4	16	10 < 16, so high = 3
2	0	3	1	5	10 > 5, so low = 2
3	2	3	2	8	10 > 8, so low = 3
4	3	3	3	12	10 < 12, so high = 2

Now low (3) > high (2) — the search area is empty. 10 is not in the list. Return -1.

---

Efficiency of Binary Search

Case	Comparisons	Explanation
Best case	1	The target is the middle element
Worst case	log₂(n)	The list is halved repeatedly
Average case	log₂(n)	Approximately log₂(n) comparisons

Binary search has a time complexity of O(log n), which is much faster than linear search's O(n) for large datasets.

Example: A list of 1,000,000 items:

• Linear search: up to 1,000,000 comparisons
• Binary search: at most 20 comparisons (since log₂(1,000,000) ≈ 20)

---

Advantages of Binary Search

• Very efficient for large sorted datasets — far fewer comparisons than linear search.
• Scales well — doubling the dataset size only adds one extra comparison.
• Predictable performance — worst case is O(log n).

Disadvantages of Binary Search

• Data must be sorted — sorting takes time and effort.
• Only works on data structures that support random access (e.g., arrays), not linked lists.
• More complex to implement than linear search.

---

Comparing Linear Search and Binary Search

Feature	Linear Search	Binary Search
Data requirement	Works on unsorted data	Requires sorted data
Best case	O(1)	O(1)
Worst case	O(n)	O(log n)
Simplicity	Very simple	More complex
Suitable for	Small or unsorted datasets	Large sorted datasets

Exam Tip: A common exam question asks you to compare linear and binary search. Always mention that binary search requires sorted data, is more efficient for large datasets, but is harder to implement. State the time complexities if asked about efficiency.

---

Key Points

• Binary search works by repeatedly halving the search area.
• It requires the data to be sorted before searching.
• Time complexity: O(log n) — much faster than O(n) for large datasets.
• Best case: 1 comparison. Worst case: log₂(n) comparisons.
• The main trade-off is that you must sort the data first.

---

Extended Worked Examples

Worked Example A: Larger Trace with 15 Elements

Consider the sorted list with indices 0–14:

Index:  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14
Value:  4   8  12  17  21  26  30  34  39  42  47  53  58  61  69

Target: 53

Iteration	low	high	mid	list[mid]	Decision
1	0	14	7	34	53 > 34 → low = 8
2	8	14	11	53	Found at index 11

Only 2 comparisons were required to locate an element in a 15-item list. For a list of 1,024 items, a maximum of 10 comparisons are needed; for 1,048,576 items, a maximum of 20. This exponential-shrinking behaviour is the hallmark of an O(log n) algorithm.

Worked Example B: Target Not in List (Extended Trace)

Using the same 15-element list above, search for 50: