4.3.4.1–4.3.4.3 - Linear, binary and binary-tree search (VB.NET)

Linear search and its stopping rule

Linear search examines entries one at a time, so it works even when the values have no ordering.

The following VB.NET function returns the first matching zero-based index, or −1 if the target is absent. Put each function in this lesson inside a module. Returning immediately on a match is what makes this a first-match search.

Function LinearSearch(values As Integer(), target As Integer) As Integer
    For index As Integer = 0 To values.Length - 1
        If values(index) = target Then Return index
    Next
    Return -1
End Function

For {18, 7, 25, 7} and target 7, index 0 fails and index 1 matches, so the result is 1. Index 3 is never examined. To find the last occurrence instead, keep a result variable, update it at each match and continue to the end.

The best case checks one value. The worst case checks all $n$ entries: the target is last or missing. Doubling $n$ can double this maximum, so worst-case time is $O(n)$. An empty array executes no loop iterations and returns −1. The extra working storage of this iterative implementation stays constant as the array grows.

Binary search on ordered data

Binary search can discard half the remaining positions only because the array is sorted by the same ordering used in its comparisons.

Maintain inclusive indices low and high. Compare the target with the middle value. If the target is smaller, no value at or to the right of the middle can be it, so use high = middle - 1. If larger, use low = middle + 1. Equality returns the middle index. The search fails when low > high; no candidate positions remain.

Function BinarySearch(values As Integer(), target As Integer) As Integer
    Dim low As Integer = 0
    Dim high As Integer = values.Length - 1
    While low <= high
        Dim middle As Integer = low + (high - low) \ 2
        If values(middle) = target Then Return middle
        If target < values(middle) Then
            high = middle - 1
        Else
            low = middle + 1
        End If
    End While
    Return -1
End Function

For {4, 9, 15, 21, 28, 34, 40} and target 34:

| low | high | middle | Value | Next action |
|---:|---:|---:|---:|---:|---|
| 0 | 6 | 3 | 21 | low becomes 4 |
| 4 | 6 | 5 | 34 | Return 5 |

With target 33, the second row sets high = 4; the next comparison is index 4, value 28. It sets low = 5, so the loop ends and returns −1. The <= condition is essential: one remaining candidate must still be checked. Subtracting/adding one excludes the middle already shown not to match and ensures progress.

Repeated halving reaches one candidate after roughly $\log_2 n$ reductions; worst-case time is $O(\log n)$. Sorting unsorted data first has its own cost, so this does not make an isolated search of any unsorted list instantly logarithmic.