Searching Algorithms

Linear Search & Binary Search — Concepts, Comparisons & Code

← Back to Sort & Search

🔍 Linear Search

Keyword: one by one

Inspects each element from left to right until the target is found or the array is exhausted. No assumptions about ordering are required.

  • Works on any array — sorted or unsorted
  • On a sorted array, an early exit is possible: once an element exceeds the target, the search can stop immediately
  • Worst-case cost: O(n) comparisons
  • Simplest search to implement

📈 Binary Search

Keyword: divide & conquer

Examines the middle element of the current range, then discards the half that cannot contain the target and repeats on the remaining half.

  • Requires a sorted array — the ordering makes discarding the wrong half safe
  • Each comparison eliminates half of the remaining candidates
  • Worst-case cost: O(log n) — dramatically faster at scale
  • Slightly more implementation logic

At a Glance

Property 🔍 Linear 📈 Binary
Requires sorted array? No — but early exit is available if sorted Yes, always
Best case O(1) — target is at index 0 O(1) — target is the first midpoint
Average case O(n) O(log n)
Worst case O(n) O(log n)
Space (iterative) O(1) O(1)
Max comparisons — n = 1,000 1,000 10
Max comparisons — n = 1,000,000 1,000,000 20
Max comparisons — n = 1,000,000,000 1,000,000,000 30

Step-by-Step Traces

Array: [2, 4, 6, 7, 9, 11]  (sorted ascending, 6 elements)

Linear Search — target = 7

Stepiarr[i]Outcome
1022 ≠ 7 → continue
2144 ≠ 7 → continue
3266 ≠ 7 → continue
437✓ 7 = 7 → found at index 3

4 comparisons — scanned element by element to the match

Linear with Early Exit — target = 5 (not in array)

Stepiarr[i]Outcome
1022 < 5 → continue
2144 < 5 → continue
3266 > 5 → early exit — not found

3 comparisons — a basic scan would check all 6 elements

Binary Search — target = 7

Stepleftrightmidarr[mid]Decision
105266 < 7 → search right half
235499 > 7 → search left half
33337✓ 7 = 7 → found at index 3

3 comparisons — each step cut the search range in half

The advantage grows with scale.
  • n = 1,000 → binary needs at most 10 comparisons; linear needs up to 1,000
  • n = 1,000,000 → at most 20 vs up to 1,000,000
  • n = 1,000,000,000 → at most 30 vs up to 1,000,000,000

The Code

Standard implementations for a sorted ascending integer array. Each function returns the index of the target, or -1 if not found.

Linear Search — basic (any array, sorted or not) 
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;        // found — return index
        }
    }
    return -1;               // target not in array
}
Linear Search with Early Exit — sorted ascending array only 
function linearSearchSorted(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
        if (arr[i] > target) {    // passed the target — no point continuing
            return -1;
        }
    }
    return -1;
}
Binary Search — sorted ascending array required 
function binarySearch(arr, target) {
    let left  = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;                  // found
        } else if (arr[mid] < target) {
            left = mid + 1;              // target must be in the right half
        } else {
            right = mid - 1;             // target must be in the left half
        }
    }
    return -1;                           // target not in array
}

↺ Recursive Versions

Recursive Linear Search — basic (any array) 
function linearSearchRecursive(arr, target, i = 0) {
    if (i >= arr.length) return -1;        // base case: exhausted the array
    if (arr[i] === target) return i;        // base case: found
    return linearSearchRecursive(arr, target, i + 1);
}
Recursive Linear with Early Exit — sorted ascending only 
function linearSearchSortedRecursive(arr, target, i = 0) {
    if (i >= arr.length) return -1;
    if (arr[i] === target) return i;
    if (arr[i] > target)  return -1;        // passed the target — early exit
    return linearSearchSortedRecursive(arr, target, i + 1);
}
Recursive Binary Search — sorted ascending required 
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) return -1;            // base case: not found
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)  return binarySearchRecursive(arr, target, mid + 1, right);
    return binarySearchRecursive(arr, target, left, mid - 1);
}
Linear Search — basic (any list, sorted or not) 
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i        # found — return index
    return -1               # target not in list
Linear Search with Early Exit — sorted ascending list only 
def linear_search_sorted(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
        if value > target:  # passed the target — no point continuing
            return -1
    return -1
Binary Search — sorted ascending list required 
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid                  # found
        elif arr[mid] < target:
            left = mid + 1              # target is in the right half
        else:
            right = mid - 1             # target is in the left half

    return -1                           # target not in list

↺ Recursive Versions

Recursive Linear Search — basic (any list) 
def linear_search_recursive(arr, target, i=0):
    if i >= len(arr): return -1          # base case: exhausted the list
    if arr[i] == target: return i        # base case: found
    return linear_search_recursive(arr, target, i + 1)
Recursive Linear with Early Exit — sorted ascending only 
def linear_search_sorted_recursive(arr, target, i=0):
    if i >= len(arr): return -1
    if arr[i] == target: return i
    if arr[i] > target: return -1        # passed the target — early exit
    return linear_search_sorted_recursive(arr, target, i + 1)
Recursive Binary Search — sorted ascending required 
def binary_search_recursive(arr, target, left=0, right=None):
    if right is None: right = len(arr) - 1
    if left > right: return -1           # base case: not found
    mid = (left + right) // 2
    if arr[mid] == target: return mid
    if arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, right)
    return binary_search_recursive(arr, target, left, mid - 1)
Linear Search — basic (any array, sorted or not) 
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;        // found — return index
        }
    }
    return -1;               // target not in array
}
Linear Search with Early Exit — sorted ascending array only 
public static int linearSearchSorted(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
        if (arr[i] > target) {    // passed the target — no point continuing
            return -1;
        }
    }
    return -1;
}
Binary Search — sorted ascending array required 
public static int binarySearch(int[] arr, int target) {
    int left  = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;                  // found
        } else if (arr[mid] < target) {
            left = mid + 1;              // target is in the right half
        } else {
            right = mid - 1;             // target is in the left half
        }
    }
    return -1;                           // target not in array
}

↺ Recursive Versions

Recursive Linear Search — basic (any array, call with i=0) 
public static int linearSearchRecursive(int[] arr, int target, int i) {
    if (i >= arr.length) return -1;        // base case: exhausted the array
    if (arr[i] == target) return i;         // base case: found
    return linearSearchRecursive(arr, target, i + 1);
}
Recursive Linear with Early Exit — sorted ascending, call with i=0 
public static int linearSearchSortedRecursive(int[] arr, int target, int i) {
    if (i >= arr.length) return -1;
    if (arr[i] == target) return i;
    if (arr[i] > target)  return -1;        // passed the target — early exit
    return linearSearchSortedRecursive(arr, target, i + 1);
}
Recursive Binary Search — sorted ascending, call with left=0, right=arr.length-1 
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;            // base case: not found
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearchRecursive(arr, target, mid + 1, right);
    return binarySearchRecursive(arr, target, left, mid - 1);
}

📊 How the Sort & Search visualizer adapts these algorithms

The functions above find an exact match in a standard ascending array. The Sort & Search visualizer makes two adjustments for its graphical demo:

  • Nearest-match instead of exact equality: Dot heights are continuous values, so the algorithm tracks the closest dot seen so far and replaces the best-match whenever a nearer one is found — rather than checking for strict equality.
  • Descending order: The sort places the largest value at index 0. This flips the binary search comparisons: when arr[mid] is larger than the target, move right; when smaller, move left — the opposite of the ascending case shown above.