DSA in Java: Searching — Linear & Binary Search (Beginner Guide)

Searching — finding whether (and where) a value exists in a collection — is one of the most fundamental operations in programming. In this lesson you'll learn the two searches every developer must know: linear search and the famous binary search. Binary search in particular is a genuine interview favourite, and it's the perfect demonstration of why O(log n) from the Big O lesson is so powerful.

Linear search: check every item

The simplest possible search: start at the beginning and look at each element until you find your target (or reach the end). It's straightforward and works on any array, sorted or not.

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;   // found → return its index
    }
    return -1;   // not found
}

In the worst case (target is last, or missing) you check all n items, so linear search is O(n). For small or unsorted data, that's perfectly fine.

Binary search: halve the problem every step

Here's where it gets clever. If your array is sorted, you can do dramatically better. Think of guessing a number between 1 and 100 where each guess tells you "higher" or "lower" — you'd guess 50 first, halving the range each time. Binary search does exactly that: check the middle, then throw away the half that can't contain the target.

int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // safe midpoint (avoids overflow)
        if (arr[mid] == target) return mid;   // found it
        if (arr[mid] < target) low = mid + 1;   // target is in the right half
        else high = mid - 1;                    // target is in the left half
    }
    return -1;   // not found
}

Why binary search is so fast

Because each step halves what's left, the number of steps grows as log₂(n) — that's O(log n). The difference is staggering:

Thirty checks to search a billion items. That's the magic of logarithmic time — and exactly why interviewers love asking about binary search.

A note on that midpoint calculation

You might wonder why we write low + (high - low) / 2 instead of the obvious (low + high) / 2. For huge arrays, low + high could exceed the maximum int value and overflow into a negative number — a classic, famous bug that lurked in Java's own library for years. The subtraction form avoids it. A small detail that quietly marks you as careful.

You don't always have to write it yourself

Java's standard library includes Arrays.binarySearch(arr, target) for sorted arrays and Collections.binarySearch(list, target) for sorted lists. In real code, reach for those. But interviewers will absolutely ask you to implement binary search by hand — so learn the mechanics above cold.

Binary search looks trivial and is deceptively easy to get wrong — off-by-one errors on low/high, or infinite loops, catch almost everyone at first (they caught me plenty). My advice: memorise this exact template — low <= high, mid + 1, mid - 1 — and practise until you can write it without thinking. It's one of the highest-return few lines of code in all of DSA: it appears directly in interviews, and its "halve the search space" idea shows up in countless harder problems too.

Key takeaways

• Linear search checks every element — O(n), works on any array.
• Binary search repeatedly halves a sorted array — O(log n), astonishingly fast.
• Use the template: low <= high, compare the middle, discard the impossible half.
• Compute the midpoint as low + (high - low) / 2 to avoid integer overflow.

← Previous: DSA Lesson 4 — Recursion & Backtracking
Next: DSA Lesson 6 — Sorting Algorithms →
↑ Back to the DSA roadmap