Searching Algorithms

Linear search (sequential search) examines each element in turn until the target is found or the list is exhausted.

FUNCTION linearSearch(arr, target)
    FOR i ← 1 TO LEN(arr)
        IF arr[i] = target THEN
            RETURN i
        ENDIF
    NEXT i
    RETURN -1    // not found
ENDFUNCTION

Worked example — search for 47 in [10, 23, 35, 47, 52, 68]:

Step	Index	Value	Result
1	1	10	10 ≠ 47, continue
2	2	23	23 ≠ 47, continue
3	3	35	35 ≠ 47, continue
4	4	47	found at index 4

Complexity:

• Best case: $O(1)$ — target is the first element
• Worst case: $O(n)$ — target is last or not present (must check every element)
• Average case: $O(n)$

Key property: works on unsorted data. No preprocessing required.

Binary search eliminates half the remaining search space at each step by comparing the target with the middle element.

Requirement: the array must be sorted in ascending order.

FUNCTION binarySearch(arr, target)
    low ← 1
    high ← LEN(arr)
    WHILE low <= high DO
        mid ← (low + high) DIV 2
        IF arr[mid] = target THEN
            RETURN mid
        ELSE IF arr[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1    // not found
ENDFUNCTION

Worked example — search for 52 in sorted array [10, 23, 35, 47, 52, 68, 79, 91] (indices 1–8):

Step	Low	High	Mid	arr[mid]	Decision
1	1	8	4	47	47 < 52 → low = 5
2	5	8	6	68	68 > 52 → high = 5
3	5	5	5	52	found at index 5

Found in 3 comparisons instead of 5 with linear search.

Complexity: $O(\log n)$ — each comparison halves the search space.

Each step cuts the remaining elements in half. Starting with $n$ elements:

Step	Elements remaining
0	$n$
1	$n/2$
2	$n/4$
$k$	$n/2^k$

The search ends when $n/2^k=1$, so $k={\log }_{2}n$. For $n=1000$, at most 10 comparisons are needed.

Comparison:

Array size	Linear search (worst)	Binary search (worst)
100	100 comparisons	7 comparisons
1000	1000 comparisons	10 comparisons
1,000,000	1,000,000 comparisons	20 comparisons

Binary search is dramatically faster for large datasets — but only if the data is sorted. Sorting costs $O(n\log n)$; if you only search once, linear search on unsorted data may be faster overall.

A binary tree search finds a value in a binary search tree (BST) using the BST ordering property:

• All values in the left subtree are less than the root
• All values in the right subtree are greater than the root

FUNCTION bstSearch(node, target)
    IF node = NULL THEN
        RETURN NOT_FOUND
    ELSE IF node.value = target THEN
        RETURN node
    ELSE IF target < node.value THEN
        RETURN bstSearch(node.left, target)
    ELSE
        RETURN bstSearch(node.right, target)
    ENDIF
ENDFUNCTION

Worked example — search for 35 in the BST:

1. Root = 47. 35 < 47 → go left
2. Node = 23. 35 > 23 → go right
3. Node = 35. Found!

Complexity:

• Average case: $O(\log n)$ — balanced BST halves the search space at each node
• Worst case: $O(n)$ — degenerate (unbalanced) tree where all nodes form a single chain

Algorithm	Data requirement	Time complexity	When to use
Linear search	Unsorted or sorted	$O(n)$	Small datasets; data changes frequently; data not sortable
Binary search	Must be sorted	$O(\log n)$	Large sorted arrays; many searches on same dataset
BST search	Must be in a BST	$O(\log n)$ avg, $O(n)$ worst	Dynamic datasets with frequent insertions and deletions

Decision guide:

• Data unsorted and won't be sorted → linear search
• Data sorted (or worth sorting for many searches) → binary search
• Data is stored in a BST (or insertion/deletion needed) → BST search

1. Applying binary search to unsorted data

Binary search only works on sorted data. Applying it to an unsorted array produces incorrect results without error. Always state the sorted precondition.

2. Mid calculation: integer division required

Mid must be an integer index: mid ← (low + high) DIV 2, not real division. Real division (/) gives 3.5 for indices 1 and 6, which is an invalid array index.

3. Off-by-one errors updating low and high

After a comparison: low ← mid + 1 (not mid) and high ← mid - 1 (not mid). Using mid instead of mid ± 1 creates an infinite loop when arr[mid] is never the target.

4. Claiming BST search is always O(log n)

BST search is $O(\log n)$ only for a balanced tree. In the worst case (inserting elements in sorted order), the BST degenerates into a linked list and search is $O(n)$.

5. Confusing binary search and BST search

Binary search operates on a sorted array using index arithmetic. BST search operates on a tree structure using node pointers. They have the same average complexity but are different algorithms on different data structures.