Searching Arrays

After this lesson, you will be able to:

• Implement linear search to find a value in an unsorted array
• Implement binary search on a sorted array
• Trace both algorithms step by step, showing comparisons at each pass
• Explain why binary search is O(log n) while linear search is O(n)
• Choose the right search algorithm based on whether data is sorted

The Search Problem

You have an array of 1,000 student IDs and need to find whether ID 42857 is in the list. Do you check every single element? Or is there a faster way?

This is one of the most fundamental operations in computer science — search engines, databases, spell checkers, and autocomplete all rely on efficient searching. Today you learn two approaches: one simple but slow, one fast but with a catch.

From CSCD 110: In Python, you used if x in my_list: and Python searched for you. In Java, there is no built-in in operator for arrays. You write the search yourself — which means you need to understand the algorithm, not just call a function.

Linear Search: Check Every Element

Start at the beginning. Check each element. If you find the target, return its index. If you reach the end, return -1 (not found).

public static int linearSearch(final int[] arr, final int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Tracing Linear Search

Given arr = {42, 17, 93, 55, 28}, searching for 55:

For Strings, use .equals() instead of ==:

public static int linearSearch(final String[] arr, final String target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i].equals(target)) {
            return i;
        }
    }
    return -1;
}

Key Insight: Linear search requires no special setup — the data does not need to be sorted. It always works. The downside: for an array of n elements, you might check all n before finding the target (or discovering it is not there). Linear search is O(n) — time grows linearly with data size.

Binary Search: Divide and Conquer

Binary search is like the number-guessing game: “I’m thinking of a number between 1 and 100.” If you guess 50 and the answer is “higher,” you have eliminated half the possibilities in one step.

Precondition: The array must be sorted. If it is not sorted, binary search gives garbage results.

The Algorithm

1. Set low = 0 and high = arr.length - 1
2. While low <= high:
   • Compute mid = (low + high) / 2
   • If arr[mid] == target: found it — return mid
   • If arr[mid] < target: target is in the right half — set low = mid + 1
   • If arr[mid] > target: target is in the left half — set high = mid - 1
3. If the loop ends, the target is not in the array — return -1

Tracing Binary Search

Given arr = {10, 20, 30, 40, 50, 60, 70, 80}, searching for 30:

Only 3 passes for an 8-element array. Linear search would need up to 8.

Implementation

public static int binarySearch(final int[] arr, final int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

Common Pitfall: Binary search only works on sorted arrays. If the array is not sorted, binary search will skip over elements and give wrong answers. Sort first with Arrays.sort() or verify the data is already sorted.

Why Binary Search Is Dramatically Faster

Each pass eliminates half the remaining elements:

Binary search is O(log n) — the number of passes is the logarithm (base 2) of the array size. For 1,024 elements: log₂(1024) = 10 passes maximum. For 1,048,576 elements: only 20 passes.

The catch: you need sorted data, and sorting takes time. If you search once, linear search may be faster overall. If you search many times, sort once and use binary search.

When to Use Which

Complete Example: Student Lookup

import java.util.Arrays;
import java.util.Scanner;

public class StudentLookup {
    public static int linearSearch(final int[] arr, final int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static int binarySearch(final int[] arr, final int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {1042, 2071, 3015, 4088, 5023, 6099, 7056, 8034};
        // Already sorted — binary search is safe

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter student ID to find: ");
        int target = scanner.nextInt();

        int index = binarySearch(ids, target);

        if (index != -1) {
            System.out.println("Found at position " + index);
        } else {
            System.out.println("Student ID " + target + " not found.");
        }
    }
}

Summary

Linear search checks every element sequentially — simple, works on any data, but O(n). Binary search halves the search space each pass — O(log n), dramatically faster, but requires sorted data.

The key algorithmic insight: binary search eliminates half the possibilities with each comparison. For 1,000,000 elements, that is 20 comparisons instead of 1,000,000.

When tracing either algorithm, track the comparisons pass by pass. For binary search, track low, high, and mid at each step.

Next lesson: Selection sort — how to put an unsorted array in order, one minimum at a time.