Introduction

Sorting organises data — searching finds data. These two skills go hand in hand: many of the best search techniques only work when the data is already sorted.

In this post, we cover the two essential search algorithms:

• Linear Search — check every element, one by one. Simple but slow.
• Binary Search — repeatedly halve the search space. Fast but requires sorted data.

Linear Search

How It Works

Imagine you dropped your keys somewhere in your house. You start at the front door and check every room, one by one, until you find them (or run out of rooms).

That is Linear Search: start at the beginning, look at each element, and stop when you find what you are looking for.

Step-by-Step Walkthrough

Find 27 in the array [14, 33, 27, 10, 45, 8].

We checked 3 elements before finding the target.

Java Implementation

public class LinearSearch {

    /**
     * Searches for a target value in an unsorted array.
     * Returns the index if found, -1 otherwise.
     */
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // found — return the index
            }
        }
        return -1; // not found
    }

    public static void main(String[] args) {
        int[] data = {14, 33, 27, 10, 45, 8};
        int result = linearSearch(data, 27);
        System.out.println(result); // Output: 2
    }
}

Complexity

| Space | $O(1)$ | |:—:|:—:|

Binary Search

How It Works

Now imagine your keys are hidden in one of 1,000 numbered lockers, and you know the lockers are sorted by some clue. Instead of opening every locker, you:

1. Go to the middle locker (#500).
2. A sign tells you whether your keys are in a locker with a higher or lower number.
3. You eliminate half the lockers and repeat.

After just 10 steps ($\log_2 1000 ≈ 10$), you have found your keys. That is the power of $O(\log n)$.

Requirements

Binary Search only works on sorted data. If the array is unsorted, you must sort it first (see our sorting posts).

Step-by-Step Walkthrough

Find 23 in the sorted array [5, 8, 12, 17, 23, 38, 42, 56, 71].

That was lucky — let’s try a harder one. Find 38.

Only 3 steps to search a 9-element array. For a million elements, it would take at most 20 steps.

Now let’s find 15 (which is NOT in the array).

Java Implementation

Iterative Version

public class BinarySearch {

    /**
     * Searches for a target in a SORTED array using Binary Search (iterative).
     * Returns the index if found, -1 otherwise.
     */
    public static int binarySearch(int[] sortedArr, int target) {
        int low = 0;
        int high = sortedArr.length - 1;

        while (low <= high) {
            // Calculate mid safely to avoid integer overflow
            int mid = low + (high - low) / 2;

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

        return -1; // target not found
    }

    public static void main(String[] args) {
        int[] sorted = {5, 8, 12, 17, 23, 38, 42, 56, 71};

        System.out.println(binarySearch(sorted, 38)); // Output: 5
        System.out.println(binarySearch(sorted, 15)); // Output: -1
    }
}

Recursive Version

public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
    // Base case: search space is exhausted
    if (low > high) return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high); // right half
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);  // left half
    }
}

Key Lines Explained

Complexity

Linear vs Binary Search

When to Use / When NOT to Use

Practice Problems

1. Binary Search – LeetCode #704 — Classic implementation practice.
2. Search Insert Position – LeetCode #35 — Find where a target would be inserted in a sorted array.
3. First Bad Version – LeetCode #278 — A creative Binary Search application.
4. Find Minimum in Rotated Sorted Array – LeetCode #153 — Binary Search on a twist.

What’s Next?

Binary Search showed us the power of reducing the search space. Next, we explore a related technique that uses two pointers to solve problems on sorted arrays and linked lists efficiently: Two Pointer Technique.