Searching

Nievergelt & Hinrichs · Ch. 4 · Algorithms and Data Structures

Binary search finds an element in a sorted array in O(log n) by halving the search space at each step. Hash tables achieve O(1) expected time by computing the position directly. Interpolation search guesses smarter when keys are uniformly distributed.

Binary search

Requires a sorted array:

Compare the target to the middle element.
If equal, done.
If less, search the left half.
If greater, search the right half.

Each step halves the search space: O(log n).

Scheme

; Binary search on a sorted list (using vector for O(1) access)
; Returns the index, or -1 if not found

(define arr (vector 2 5 8 12 15 19 23 27 31 35))

(define (binary-search vec target lo hi)
  (if (> lo hi) -1
      (let ((mid (quotient (+ lo hi) 2)))
        (cond ((= (vector-ref vec mid) target) mid)
              ((< (vector-ref vec mid) target)
               (binary-search vec target (+ mid 1) hi))
              (else
               (binary-search vec target lo (- mid 1)))))))

(display "Search for 15: index ")
(display (binary-search arr 15 0 9)) (newline)
(display "Search for 27: index ")
(display (binary-search arr 27 0 9)) (newline)
(display "Search for 10: index ")
(display (binary-search arr 10 0 9))

Hash tables

Compute a hash function h(key) to find the position directly. Expected O(1) for insert, delete, and lookup. Worst case O(n) if many keys collide. The trade-off: O(1) time for no ordering.

Scheme

; Simple hash table with chaining
; Hash function: key mod table-size

(define table-size 7)

(define (make-table) (make-vector table-size (list)))

(define (hash-fn key) (modulo key table-size))

(define (insert! tbl key)
  (let ((idx (hash-fn key)))
    (vector-set! tbl idx (cons key (vector-ref tbl idx)))))

(define (lookup tbl key)
  (let ((idx (hash-fn key)))
    (member key (vector-ref tbl idx))))

(define tbl (make-table))
(insert! tbl 15)
(insert! tbl 22)  ; 22 mod 7 = 1
(insert! tbl 8)   ; 8 mod 7 = 1 (collision with 22)
(insert! tbl 31)

(display "Lookup 15: ") (display (if (lookup tbl 15) "found" "not found")) (newline)
(display "Lookup 8:  ") (display (if (lookup tbl 8) "found" "not found")) (newline)
(display "Lookup 10: ") (display (if (lookup tbl 10) "found" "not found"))

Interpolation search

When keys are uniformly distributed, guess where the target is by linear interpolation. Expected O(log log n) for uniform data. Falls back to O(n) in the worst case.

Neighbors

Cross-references

⚙ Ch.5 — trees: BSTs give O(log n) search with ordering

← Sorting by june.kim Trees →