Courses Edexcel iGCSE Computer Science Algorithms Binary Search

Binary Search

Introduction to Binary Search

What is Binary Search?

Binary search is a divide & conquer search algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search space in half until the target element is found or determined to be absent.

Binary search starts by comparing the target element with the middle element of the array. If they are equal, the search is complete. If the target element is smaller, the search continues on the lower half of the array; otherwise, it continues on the upper half.

This process is repeated until the target element is found or the search space is empty.

Binary Search Visualisation

What is a binary search?

{"answers": {"A": "B - A search algorithm that divides the data in half", "B": "A - A search algorithm that tries every possibility", "C": "D - A search algorithm that checks each element in order", "D": "C - A search algorithm that follows a set path"}, "question_text": "What is a binary search?", "correct_answer": "A"}

What is the key difference between binary search and linear search?

{"answers": {"A": "Linear search is only used for sorting, while binary search is used for searching", "B": "Binary search has a worse-case running time of O(n), while linear search has a worse-case running time of O(log n)", "C": "Binary search can only be used with integer values, while linear search can be used with any data type", "D": "Binary search requires the list to be in a specific order, while linear search does not"}, "question_text": "What is the key difference between binary search and linear search?", "correct_answer": "D"}

Pros and Cons of Binary Search

Pros

Efficient searching algorithm because it divides the search space in half with each comparison
It can quickly find a desired element in a large data set

Cons

Requires a sorted array, it cannot handle unsorted or unordered data
Implementation is more complex than a linear search

In Binary Search, search interval is repeatedly [[divided]] in half.

{"cloze_text": "In Binary Search, search interval is repeatedly [[divided]] in half."}

The time complexity of Binary Search is [[O(log n)]].

{"cloze_text": "The time complexity of Binary Search is [[O(log n)]]."}

{"keyword": "Divide and Conquer", "definition": "A problem-solving strategy that involves breaking a problem into smaller sub-problems, solving them independently and combining their solutions."}

Binary Search Python Implementation

Here is an example of Binary search python script. This script uses recursion, because the search function calls itself.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example usage
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search(array, target)

if result != -1:
    print("Element found at index", result)
else:
    print("Element not found")

Review: Fill in the Blanks

is a commonly used algorithm to find a efficiently in a . It follows the approach, dividing the array into smaller subproblems. This technique can be implemented using either or recursion.

In binary search, the array is divided into two parts by finding the . The mid-point is the at the middle of the array. The target element is then compared with the element at the mid-point. If they are equal, the search is successful, and the index of the target element is returned. If the target element is smaller, the search continues on the left half of the array. Likewise, if the target element is larger, the search continues on the right half of the array.

Binary search has a of O(log n), where n is the size of the sorted array. This logarithmic time complexity arises from dividing the search space in half with each . Additionally, binary search has a of O(1), as it only needs a few variables to store the left and right boundaries as indices.

Click the keywords below to fill in the blanks:

Target Element Divide And Conquer Mid-Point Sorted Array Binary Search Time Complexity Index Space Complexity Iteration Comparison

✓ All blanks filled correctly! Great job!