The binary search algorithm

This lesson covers implementing binary search in Julia, 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. The ÷ integer-division operator is a characteristic Julia touch.

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

function binary_search(arr, target)
    low, high = 1, length(arr)
    while low <= high
        mid = (low + high) ÷ 2
        if arr[mid] == target
            return mid
        elseif arr[mid] < target
            low = mid + 1
        else
            high = mid - 1
        end
    end
    return -1
end

nums = [1, 3, 5, 7, 9, 11]
println(binary_search(nums, 7))
println(binary_search(nums, 4))

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Julia 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).