2.3.1 - Linear and binary search

Scan until the first match or the end

Linear search examines items in sequence. Compare each with the target; on a match return its index, otherwise move to the next. If every item has been examined without a match, return an explicit not-found sentinel. Our integer sentinel is -1, because valid zero-based indices are 0 through length-1. Do not use truthiness to interpret a returned index: 0 is a valid match even though it is false-like in Python. Also, do not index the list with -1 before checking it, since Python would select its final item.

No sorting precondition is needed. For [14,5,9,5] and target 5, comparisons are index 0 (14, not equal) then index 1 (5, equal), so the result is 1. The second 5 at index 3 is not reached. This version therefore returns the first matching index. An absent target 7 causes all four items to be compared before -1 is returned. An empty list needs no comparisons and returns -1.

function linearSearch(values, n, target)
    for i = 0 to n - 1
        if values[i] == target then
            return i
        endif
    next i
    return -1
endfunction

The exhausted result comes after the loop, not in the else of the first comparison. That misplaced return would treat a nonmatching first item as proof of absence.

def linear_search(values, target):
    for i in range(len(values)):
        if values[i] == target:
            return i
    return -1

print(linear_search([14, 5, 9, 5], 5))
print(linear_search([14, 5, 9, 5], 7))

1
-1

Explore early stopping

Predict the returned index and number of target-equality comparisons, then run this ungraded scan. Its counter counts only value == target, excluding loop controls. A match stops the scan; an absent target requires exhaustion.

Keep an inclusive interval of possible matches

Binary search needs data sorted by the same comparison used for searching. On an ascending random-access list, compare the target with the middle item of the remaining interval. A smaller target can only be to its left; a larger target can only be to its right. Discard the middle too once it is known not to match.

Our bounds are inclusive: low = 0, high = length - 1; middle is (low + high) // 2, rounding down for an even-sized interval. If the middle is equal, return its index. If its value is smaller than the target, set low to mid+1; otherwise set high to mid-1. Repeat while low <= high. When low > high, the possible-match interval is empty and the target is absent.

Search [3,8,12,17,23,31,42] for 23:

Here a probe means examining one midpoint item. The code can perform both an equality comparison and an ordering comparison on that item; probe counts do not claim just one language-level comparison per loop.

For absent target 20 in the same list, the first two probes are identical, but the third sees 23 and sets high to 3. Now low=4 exceeds high=3, so return -1 without another probe. Using low=mid or high=mid could retain the already rejected item and fail to shrink a one-item interval.

The invariant is that, if a match exists, one remains inside the current interval. Ordered data makes each discarded portion safe. On unsorted [9,1,7], target 9 is compared with midpoint 1, then 7, and wrongly declared absent: the ordering argument failed. Binary search does not itself sort or validate the list.

Implement found and exhausted outcomes

The comparison branches must either finish the search or make the interval strictly smaller. The implementation below assumes an ascending list of mutually comparable values with constant-time indexed access and uses the lower midpoint convention.

function binarySearch(values, n, target)
    low = 0
    high = n - 1
    while low <= high
        mid = (low + high) DIV 2
        if values[mid] == target then
            return mid
        elseif values[mid] < target then
            low = mid + 1
        else
            high = mid - 1
        endif
    endwhile
    return -1
endfunction

DIV is integer division in this pseudocode; Python uses //. Both forms compute an index, not a fractional position.

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([3, 8, 12, 17, 23, 31, 42], 23))
print(binary_search([3, 8, 12, 17, 23, 31, 42], 20))