Binary Search

Binary Search in ARM64

Binary search is one of the most fundamental algorithms in computer science. It finds a target value in a sorted array by repeatedly halving the search space. This lesson combines nearly every concept from the course: memory access, loops, comparisons, arithmetic, and functions.

The Algorithm

Given a sorted array and a target value:

1. Set lo = 0 and hi = length - 1
2. While lo <= hi: a. Compute mid = (lo + hi) / 2 (use unsigned division) b. If arr[mid] == target, return mid c. If arr[mid] < target, set lo = mid + 1 d. If arr[mid] > target, set hi = mid - 1
3. If the loop ends, the target was not found

Pseudocode

function binary_search(arr, len, target):
    lo = 0
    hi = len - 1
    while lo <= hi:
        mid = (lo + hi) / 2
        val = arr[mid]
        if val == target:
            return mid
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  // not found

Implementation Notes

Computing the midpoint: Use ADD and LSR (logical shift right by 1 is the same as dividing by 2):

ADD X3, X0, X1       // X3 = lo + hi
LSR X3, X3, #1       // X3 = (lo + hi) / 2

Loading from the array: Use LDRB with register offset:

LDRB W4, [X5, X3]   // Load arr[mid] (byte array)

Updating lo and hi: After comparing arr[mid] with the target:

CMP W4, W6           // compare arr[mid] with target
B.EQ found           // exact match!
B.LT go_higher       // arr[mid] < target, search right half
// Otherwise arr[mid] > target, search left half
SUB X1, X3, #1       // hi = mid - 1
B search_loop

go_higher:
ADD X0, X3, #1       // lo = mid + 1
B search_loop

Time Complexity

"Scanning for life forms" -- like Data methodically scanning a planet, binary search eliminates half the possibilities with each comparison. Fascinatingly efficient.

Binary search runs in O(log n) time. For an array of 1 million elements, it needs at most 20 comparisons. Linear search would need up to 1 million. This is the power of halving the search space.

Your Task

Implement binary search on the sorted byte array [2, 5, 8, 12, 16, 23, 38, 42, 55, 67] (10 elements). Search for the target value 23. It is at index 5. Print the index followed by a newline.