Searching algorithms

A linear search checks each item in turn, from the beginning, until it finds the target or reaches the end. It works on sorted or unsorted data. With six items it may need to check all six.

The animation checks for 6 in 7, 3, 9, 2, 6, 4 and highlights each item as it is compared.

Assume numbers contains six items and target is the value being searched for. The ERL and Python versions return the first matching index, or -1 if it is not present:

position = -1
FOR i = 0 TO 5
    IF numbers[i] == target AND position == -1 THEN
        position = i
    ENDIF
NEXT i

position = -1
for i in range(len(numbers)):
    if numbers[i] == target:
        position = i
        break

A binary search repeatedly checks the middle item and discards the half that cannot contain the target. It is quicker than checking every item on a long list, but the data must already be sorted.

The animation searches for 7 in 2, 4, 6, 7, 9, 12. Each step compares the middle value and keeps only the possible half.

The following ERL and Python algorithms return the target's index, or -1 if it is absent. numbers is the same sorted list in both:

low = 0
high = 5
position = -1
WHILE low <= high
    middle = (low + high) DIV 2
    IF numbers[middle] == target THEN
        position = middle
        high = low - 1
    ELSE IF numbers[middle] < target THEN
        low = middle + 1
    ELSE
        high = middle - 1
    ENDIF
ENDWHILE

low = 0
high = len(numbers) - 1
position = -1
while low <= high:
    middle = (low + high) // 2
    if numbers[middle] == target:
        position = middle
        break
    elif numbers[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

Binary search halves the items left to search at every check, so even a very long sorted list needs only a few checks. Linear search is the only choice when the data isn't sorted, unless it is sorted first, which takes time of its own.