Binary Search

2.1 Definition of Binary Search and Its Main Concepts

Binary search is an algorithm for finding an element in a sorted array, which works by dividing the array in half. This algorithm is significantly more efficient than a linear search for large arrays because it reduces the number of checks by dividing the array into two parts at each iteration.

Main concepts:

• Sorted array: Binary search only works on sorted arrays.
• Halving: The algorithm compares the desired element with the element in the middle of the array.
• Recursive or iterative division: If the desired element is less than the middle one, the search continues in the left half of the array, otherwise — in the right half.
• Termination condition: The search stops when the element is found or the search range becomes empty.

Important! Binary search requires a sorted array.

For binary search to work correctly, the input data must be sorted in ascending order. This is the main and only requirement because the algorithm relies on the fact that the elements of the array are ordered. Thanks to this, it can efficiently eliminate half of the elements at each search step.

Example of a sorted array:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Step-by-Step Implementation of Binary Search

How binary search works:

1. Initialization: Set the initial search boundaries (left and right boundaries of the array).
2. Select middle element: Find the index of the middle element of the array.
3. Comparison: Compare the middle element with the target value.
4. Update boundaries:
   1. If the middle element equals the target value, return its index.
   2. If the target value is less than the middle element, update the right boundary of the search.
   3. If greater — update the left boundary.
5. Repeat: Repeat steps 2-4 until the element is found or until the left boundary exceeds the right.

Step-by-step algorithm:

1. Initialization: Set left to 0 and right to len(arr) - 1.
2. Calculate middle element: mid = (left + right) // 2
3. Compare with target element:
   1. If arr[mid] == target, return mid
   2. If arr[mid] < target, update left = mid + 1
   3. If arr[mid] > target, update right = mid - 1
4. Repeat: Return to step 2 as long as left <= right
5. If element is not found: Return -1

Iterative binary search implementation in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Usage example:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 3

2.3 Time Complexity of Binary Search O(log n)

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This means that at each step, the algorithm halves the number of elements, which significantly speeds up the search compared to linear search, which has a time complexity of O(n).

Time complexity analysis:

• Best case: Element found on the first step, O(1).
• Average case: O(log n).
• Worst case: Element found on the last step or not present, O(log n).

Example for time complexity analysis:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Element {target} found at index {index}")  # Output: Element 7 found at index 3

# The algorithm made 3 steps (logarithm of 7 elements) to find the element, 
# which corresponds to O(log n)

Graphical representation of complexity:

Imagine an array of 16 elements.

Suppose we are searching for the element 15, then the steps are as follows:

First step. Check the middle element (8 elements remain).

Second step. Check the middle element in the remaining half (4 elements remain).

Third step. Check the middle element in the remaining half (2 elements remain).

Fourth step. Check the last element (1 element remains).

As a result, the algorithm will perform 4 steps for an array of 16 elements, which corresponds to the logarithm base 2 of 16, i.e., log2(16) = 4. This is logarithmic complexity O(log n).

2

Task

Python SELF EN, level 53, lesson 1

Locked

Binary Search

Binary Search

Open