Binary search locates a value in a sorted, index-accessible collection by checking the middle element and discarding the half that cannot contain the target. section 2.1
Apply the technique by maintaining a candidate range:
- Set low to the first index and high to the last index. section 2.1
- While low is no greater than high, calculate the middle index. section 2.1
- If the middle value is less than the target, move low above it; if greater, move high below it. section 2.1
- Return true on equality and false when the range becomes empty. section 2.1
Searching sorted words
In ["cat", "dog", "kangaroo", "llama", "rabbit", "rat", "zebra"], checking "llama" shows that "rat" must lie in the later half. Repeating the comparison narrows the range until "rat" is found. A Swift implementation generalizes this idea with binaryContains<T: Comparable>. section 2.1
func binaryContains(_ array: Gene, item: Codon) -> Bool {
var low = 0
var high = array.count - 1
while low <= high {
let mid = (low + high) / 2
if array[mid] < item {
low = mid + 1
} else if array[mid] > item {
high = mid - 1
} else {
return true
}
}
return false
}
The complete Swift implementation makes the shrinking bounds, midpoint calculation, comparison branches, and termination condition directly inspectable. section 2.1
The method requires ordering and constant-time index access, making a sorted Swift Array suitable. It can search sorted Gene data after sorting it, while an unsorted collection does not meet the stated conditions. section 2.1
