The binary search algorithm

This lesson covers implementing binary search in Objective-C, with the aim of understanding how to find a value efficiently.

Binary search finds a value efficiently in already-sorted data. Picture opening a dictionary in the middle and halving the range each time.

The sample code calculates the middle mid from the two positions low and high, compares it with the target, and narrows the range by updating low or high. Note [arr[mid] integerValue], which takes the integer out of an NSNumber.

A common early stumble is that binary search requires the array to be sorted beforehand. That is a precondition, so do not forget to sort first.

In professional work, the idea behind binary search is applied widely wherever a particular value has to be found quickly in a large body of data.

📖 Reference code

NSInteger binarySearch(NSArray *arr, NSInteger target) {
    NSInteger low = 0, high = arr.count - 1;
    while (low <= high) {
        NSInteger mid = (low + high) / 2;
        NSInteger val = [arr[mid] integerValue];
        if (val == target) return mid;
        if (val < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

NSArray *nums = @[@1, @3, @5, @7, @9, @11];
NSLog(@"%ld", (long)binarySearch(nums, 7));
NSLog(@"%ld", (long)binarySearch(nums, 4));

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Objective-C directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).