Binary Search

Definition

Binary search is a searching algorithm that works on a sorted array or list by comparing the target value with the middle element and repeatedly narrowing the search range to the left half or right half until the target is found or the range becomes empty.

It relies on the fact that the data must be in sorted order, because only then can the algorithm decide which half can be discarded safely.

Main Content

1. Sorted Data Requirement

• Binary search can only work correctly if the data is already sorted in ascending or descending order.
• If the data is unsorted, the algorithm cannot determine whether to move left or right, because the ordering rule is missing.

Example:
Suppose you want to search for 23 in the sorted list:

[5, 12, 18, 23, 31, 45, 50]

The middle element is checked first, and based on whether 23 is smaller or larger, the search continues in the appropriate half.

Why sorting matters:

• If the list were [23, 5, 50, 12, 31, 18, 45], the middle comparison would not give reliable direction.
• Therefore, sorting is a necessary condition before applying binary search.

Key idea:
Binary search uses the order of the elements to eliminate half the search space at each step.

2. Middle Element Comparison

• The heart of binary search is the comparison with the middle element of the current search range.
• After checking the middle value, the algorithm decides:
• If the target is equal to the middle element, the search is successful.
• If the target is smaller, the search continues in the left half.
• If the target is larger, the search continues in the right half.

Example:
For the sorted array:

[2, 4, 6, 8, 10, 12, 14]

If searching for 10:

• Middle element = 8
• Since 10 > 8, ignore the left half.
• Search only in [10, 12, 14]
• Middle of this part is 12
• Since 10 < 12, move to [10]
• Target found

Why this is efficient:

• Each comparison removes a large portion of the remaining elements.
• This makes binary search much faster than checking every element.

Important observation:
The middle position is usually calculated carefully to avoid overflow in some programming languages:

• mid = low + (high - low) / 2

3. Search Space Reduction and Complexity

• Binary search is efficient because it reduces the search space by half in every iteration or recursive call.
• This halving process leads to a logarithmic time complexity.

Time complexity:

• Best case: O(1) if the target is found at the middle in the first comparison
• Average case: O(log n)
• Worst case: O(log n)

Space complexity:

• Iterative binary search: O(1)
• Recursive binary search: O(log n) due to function call stack

Example of halving:
For an array of 16 elements:

• After 1 comparison, at most 8 elements remain
• After 2 comparisons, at most 4 elements remain
• After 3 comparisons, at most 2 elements remain
• After 4 comparisons, only 1 element remains

This shows how quickly the search region becomes very small.

ASCII visualization of the halving idea:

Initial search range:
[ 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 ]

Check middle -> 7

If target > 7:
            [ 9 | 11 | 13 | 15 ]

Check middle -> 11

If target < 11:
            [ 9 ]

Working / Process

1. Start with the full sorted array

• Set two pointers or boundaries: low at the beginning and high at the end.
• These boundaries represent the current search interval.
• Initially, every element is considered possible.

2. Find the middle element and compare

• Compute the middle index of the current interval.
• Compare the target value with the middle value.
• If they match, the element has been found and the search stops.

3. Narrow the search range and repeat

• If the target is smaller than the middle element, move high to mid - 1.
• If the target is larger than the middle element, move low to mid + 1.
• Repeat the process until the element is found or low > high, which means the element is not present.

Example walkthrough:
Search for 25 in:

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

• low = 0, high = 6
• mid = 3, value = 25
• Target found immediately

Another example, search for 30:

• low = 0, high = 6
• mid = 3, value = 25
• 30 > 25, so search right half
• New range: [30, 35, 40]
• mid = 5, value = 35
• 30 < 35, so search left half
• New range: [30]
• Found target

Termination condition:
The search ends when the interval becomes invalid:

• low > high
• This means the target does not exist in the array

Advantages / Applications

Very fast on large sorted data

• Binary search dramatically reduces the number of comparisons.
• It is ideal when the dataset is large and already sorted.

Useful in many practical problems

• Searching in dictionaries or contact lists
• Finding a specific record in databases
• Looking up items in sorted tables
• Locating insertion points in ordered sequences

Foundation for advanced algorithms

• Many algorithms use binary search as a subroutine.
• It is used in problems like:
  • finding the first or last occurrence of a value
  • searching in rotated sorted arrays
  • determining boundaries in optimization problems
  • searching answers in monotonic problem spaces

Common applications:

• Sorted array search
• Finding lower bound and upper bound
• Checking membership in ordered collections
• Efficient lookups in binary search trees
• Search in real-world systems where ordered access is important

Advantages over linear search:

• Linear search checks elements one by one and takes O(n) time.
• Binary search reduces the work to O(log n) time.
• For large datasets, this difference is significant.

Summary

• Binary search is a fast method for finding an item in a sorted list by repeatedly dividing the search range in half.
• It works by comparing the target with the middle element and eliminating the irrelevant half each time.
• It is efficient, simple, and widely used in searching and problem-solving.
• Important terms to remember: sorted data, middle element, search interval, low, high, mid, logarithmic time