Tutorial: Binary Search timer 2s memory 512MB

[Divide and Conquer Algorithm]

This is an algorithm (method) that solves a problem by breaking it down into smaller sub-problems when the size of the original problem is too large to handle at once.

Representative examples include Binary Search, Quick Sort, and Merge Sort.

[Binary Search]

The Binary Search algorithm is a type of divide-and-conquer algorithm used to quickly find a target value or its position (index) within a sorted data list.

Suppose we have a sorted array A[] and we want to find a target value. Let the index of the first element be low and the index of the last element be high.

Binary Search Process

1. Calculate the middle index (mid) of the current search range:

   mid = (low + high) / 2

2. Compare the value at A[mid] with the target:

   • (1) If A[mid] == target: You have found the target or its position.

   • (2) If A[mid] < target: Adjust the search range by setting low = mid + 1.

   • (3) If A[mid] > target: Adjust the search range by setting high = mid - 1.

3. Repeat steps 1 and 2 as long as the search range exists and the target has not been found.

   • If low > high (no search range remains), the target value does not exist in the array.

Performance

In this process, the search range is reduced by half or more in every loop. The following table compares the number of data elements to the maximum number of searches required:

As the amount of data doubles, the number of searches increases by only 1. Therefore, the number of searches relative to the number of data can be generalized as log_2(n) + 1. This shows significantly better performance compared to Sequential Search.

[Binary Search Pseudocode]

Loop Version

binarySearch (A[], low, high, target):
    while low <= high:
        mid = (low + high) / 2
        if A[mid] == target:
            return mid

        if A[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return -1

Recursive Version

binarySearchRecur (A[], low, high, target):
    if low > high:
        return -1

    mid = (low + high) / 2

    if A[mid] == target:
        return mid

    if A[mid] > target:
        return binarySearchRecur(A, low, mid - 1, target)

    return binarySearchRecur(A, mid + 1, high, target)

[Problem]

Given N pieces of sorted data and Q queries, write a program to find the position (index) of the target value within the sorted data.