Searching and Sorting: Choose the Right Approach

If someone hands you a phone directory and asks you to find a name, you do not read from page one. You open it in the middle, see whether your name comes before or after, and throw away half the book. Then you do it again. In a few moves you have found it, even in a book with a million names.

This works for one reason: the names are sorted. Sorting is what makes fast searching possible, and fast searching is why we sort. This article covers both halves. You will learn how to write binary search without the off-by-one bugs that catch even experienced programmers, how to adapt it, and how the main sorting algorithms work and when to use each.

• Linear search, and when it is the right choice.
• Binary search with a clear invariant, safe midpoint, and boundary handling.
• Lower bound and upper bound, for first occurrence, insertion position and counts.
• Binary search on an answer.
• Insertion sort, merge sort and quick sort, and the vocabulary of sorting: stable, in place, comparison-based.
• How to sort in Java using Arrays.sort, comparators and 2D arrays.

Linear search checks elements one by one until it finds the target or runs out. It is O(n). Use it when:

• the data is not sorted and you only search once;
• the collection is small;
• you are searching a structure that has no fast random access, such as a linked list.

If you will search the same data many times, sorting once and then using binary search (or building a HashSet) pays off.

Binary search works on a sorted array. Look at the middle element:

• if it equals the target, you are done;
• if it is smaller than the target, the target can only be to the right, so discard the left half;
• if it is larger, the target can only be to the left, so discard the right half.

Repeat on the remaining half. After k steps at most n / 2^k elements remain, so after about log2(n) steps there is nothing left to check. The time is O(log n): for a million elements, about 20 steps; for a billion, about 30.

Two requirements, both essential:

1. The array must be sorted (in the same order your comparisons assume).
2. You need random access to the middle in O(1). Binary search on a linked list gains nothing.

Most binary search bugs come from mixing conventions. Pick one and stay consistent. In this section we use a closed interval: the target, if present, lies in a[lo..hi] with both ends included.

Invariant: if the target is in the array, it is in a[lo..hi].

• The loop runs while the interval is not empty: lo <= hi.
• The middle is mid = lo + (hi - lo) / 2.
• If a[mid] < target, then mid and everything left of it is too small, so lo = mid + 1.
• If a[mid] > target, then mid and everything right of it is too big, so hi = mid - 1.
• When the interval becomes empty, the target is not there.

Every update excludes mid, so the interval strictly shrinks. That is why the loop must end.

You may have seen mid = (lo + hi) / 2. It is wrong when lo + hi exceeds Integer.MAX_VALUE. The sum wraps to a negative number, and the resulting mid is negative, causing an ArrayIndexOutOfBoundsException or worse. Writing lo + (hi - lo) / 2 avoids the problem, because hi - lo is never larger than hi. For ordinary arrays this bug is rare, but a famous version of it sat in widely-used library code for years, and interviewers like to ask about it.

// File: Main.javapublic class Main {    static int binarySearch(int[] a, int target) {        int lo = 0;        int hi = a.length - 1;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] == target) {                return mid;            }            if (a[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return -1;    }    public static void main(String[] args) {        int[] a = {1, 3, 5, 7, 9, 11};        System.out.println(binarySearch(a, 7) + " " + binarySearch(a, 1) + " " + binarySearch(a, 11) + " " + binarySearch(a, 4));        System.out.println(binarySearch(new int[] {}, 3) + " " + binarySearch(new int[] {5}, 5) + " " + binarySearch(new int[] {5}, 4));        int lo = 1_500_000_000;        int hi = 2_000_000_000;        System.out.println("(lo + hi) / 2 = " + (lo + hi) / 2);        System.out.println("lo + (hi - lo) / 2 = " + (lo + (hi - lo) / 2));    }}

3 0 5 -1-1 0 -1(lo + hi) / 2 = -397483648lo + (hi - lo) / 2 = 1750000000

The last two lines show the overflow: lo + hi is 3.5 billion, which does not fit in an int, so the "obvious" midpoint is negative.

Dry run for target 7 in [1, 3, 5, 7, 9, 11]:

For a missing target such as 4: the interval shrinks until lo > hi, and we return -1.

With duplicates, "find the target" is ambiguous: which one? The more useful questions are:

• Lower bound: the first index i with a[i] >= target. (Where would target be inserted to keep the array sorted, before any equal elements?)
• Upper bound: the first index i with a[i] > target.

Then:

• the first occurrence of target is at lowerBound, if a[lowerBound] == target;
• the last occurrence is at upperBound - 1;
• the count of target is upperBound - lowerBound;
• the insertion position is lowerBound.

For these we use a half-open interval [lo, hi), where hi is one past the last candidate, and the answer can be a.length (meaning "none of them qualify"). The invariant is: the answer lies in [lo, hi]. We update hi = mid (not mid - 1), because mid itself might be the answer, and we stop when lo == hi.

// File: Main.javapublic class Main {    // First index i with a[i] >= target, or a.length if there is none.    static int lowerBound(int[] a, int target) {        int lo = 0;        int hi = a.length;        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] < target) {                lo = mid + 1;          // mid is too small to be the answer            } else {                hi = mid;              // mid might be the answer, keep it            }        }        return lo;    }    // First index i with a[i] > target, or a.length if there is none.    static int upperBound(int[] a, int target) {        int lo = 0;        int hi = a.length;        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] <= target) {                lo = mid + 1;            } else {                hi = mid;            }        }        return lo;    }    // Largest x such that x * x <= n. This is a binary search on the answer, not on an array.    static int floorSqrt(int n) {        int lo = 0;        int hi = n;        int best = 0;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            if ((long) mid * mid <= n) {      // long, so mid * mid cannot overflow                best = mid;                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return best;    }    public static void main(String[] args) {        int[] a = {1, 2, 2, 2, 3, 5};        System.out.println("lower(2)=" + lowerBound(a, 2) + " upper(2)=" + upperBound(a, 2) + " count=" + (upperBound(a, 2) - lowerBound(a, 2)));        System.out.println("insert 4 at " + lowerBound(a, 4) + ", insert 0 at " + lowerBound(a, 0) + ", insert 9 at " + lowerBound(a, 9));        System.out.println(floorSqrt(0) + " " + floorSqrt(1) + " " + floorSqrt(8) + " " + floorSqrt(16) + " " + floorSqrt(Integer.MAX_VALUE));    }}

lower(2)=1 upper(2)=4 count=3insert 4 at 5, insert 0 at 0, insert 9 at 60 1 2 4 46340

Walk through lowerBound(a, 2) on [1, 2, 2, 2, 3, 5]:

The first 2 is at index 1. The same loop with <= in the comparison gives the upper bound, 4. So there are 4 - 1 = 3 copies of 2.

Binary search is not only for arrays. Whenever you can define a yes/no question about a number x that is monotonic (it is "no, no, no, ..., yes, yes, yes" as x grows), you can binary search for the boundary. floorSqrt above is the simplest example: "is x * x <= n?" is true for small x and false for large x. We will use this technique again in the exercises, for a shipping-capacity problem. The structure is always the same:

1. Define the range of possible answers.
2. Write a feasible(x) check.
3. Binary search for the smallest (or largest) feasible x.

Stability matters when you sort by one field after another. If you sort employees by name, and then (stably) by department, each department stays sorted by name.

Think of sorting a hand of playing cards. You pick up cards one at a time, and slide each into its correct place among the cards already in your hand. The left part of the array is always sorted.

Dry run on [5, 2, 4, 6, 1, 3]. The sorted part grows by one element each step:

On sorted input the inner while never runs, so it is O(n). On reversed input every key moves all the way, which is O(n^2).

Divide and conquer: split the array in half, sort each half (recursively), then merge the two sorted halves (the same merge you wrote in the arrays article). The base case is an array of 0 or 1 elements, already sorted.

[38, 27, 43, 3] split         -> [38, 27]        [43, 3] split again   -> [38] [27]       [43] [3] merge         -> [27, 38]        [3, 43] merge         -> [3, 27, 38, 43]

There are log2(n) levels of splitting, and merging all the pieces at one level costs O(n), so the total is O(n log n) in every case. It uses a temporary array of size n. Because the merge takes from the left half on ties, it is stable.

Choose a pivot. Rearrange the array (partition) so every element smaller than the pivot is on its left and every larger one on its right. The pivot is then in its final position. Sort the left and right parts recursively.

The version below (Lomuto partition) moves the pivot to the end, scans through the rest, and swaps each smaller element into a growing "smaller than pivot" region at the front. It uses the middle element as the pivot to avoid the bad case of already sorted input.

On average the splits are reasonably balanced, giving O(n log n). If the pivot is always the smallest or largest element, one side is empty and the depth is n, which is the O(n^2) worst case. This simple version also slows down on arrays with many equal values, because elements equal to the pivot all land on one side. Production sorts use better pivot rules and three-way partitioning. In an interview, mention the worst case and that a random pivot makes it unlikely.

// File: Main.javaimport java.util.Arrays;public class Main {    static void insertionSort(int[] a) {        for (int i = 1; i < a.length; i++) {            int key = a[i];            int j = i - 1;            while (j >= 0 && a[j] > key) {                a[j + 1] = a[j];          // shift larger elements one place right                j--;            }            a[j + 1] = key;        }    }    static void mergeSort(int[] a) {        if (a.length < 2) {            return;        }        mergeSort(a, new int[a.length], 0, a.length - 1);    }    private static void mergeSort(int[] a, int[] temp, int lo, int hi) {        if (lo >= hi) {            return;        }        int mid = lo + (hi - lo) / 2;        mergeSort(a, temp, lo, mid);        mergeSort(a, temp, mid + 1, hi);        merge(a, temp, lo, mid, hi);    }    private static void merge(int[] a, int[] temp, int lo, int mid, int hi) {        System.arraycopy(a, lo, temp, lo, hi - lo + 1);        int i = lo;        int j = mid + 1;        for (int k = lo; k <= hi; k++) {            if (i > mid) {                a[k] = temp[j++];            } else if (j > hi) {                a[k] = temp[i++];            } else if (temp[j] < temp[i]) {    // strictly less, so ties come from the left: stable                a[k] = temp[j++];            } else {                a[k] = temp[i++];            }        }    }    static void quickSort(int[] a) {        quickSort(a, 0, a.length - 1);    }    private static void quickSort(int[] a, int lo, int hi) {        if (lo >= hi) {            return;        }        int p = partition(a, lo, hi);        quickSort(a, lo, p - 1);        quickSort(a, p + 1, hi);    }    private static int partition(int[] a, int lo, int hi) {        swap(a, lo + (hi - lo) / 2, hi);       // move the middle element to the end as the pivot        int pivot = a[hi];        int store = lo;                        // everything before store is smaller than the pivot        for (int i = lo; i < hi; i++) {            if (a[i] < pivot) {                swap(a, i, store);                store++;            }        }        swap(a, store, hi);                    // put the pivot in its final place        return store;    }    private static void swap(int[] a, int i, int j) {        int temp = a[i];        a[i] = a[j];        a[j] = temp;    }    public static void main(String[] args) {        int[][] tests = {            {5, 2, 4, 6, 1, 3},            {},            {7},            {3, 3, 3, 3},            {-5, 10, 0, -5, 8},            {1, 2, 3, 4, 5},            {9, 8, 7, 6, 5, 4, 3, 2, 1},            {Integer.MAX_VALUE, Integer.MIN_VALUE, 0}        };        for (int[] test : tests) {            int[] expected = test.clone();            Arrays.sort(expected);            int[] x = test.clone();            int[] y = test.clone();            int[] z = test.clone();            insertionSort(x);            mergeSort(y);            quickSort(z);            boolean ok = Arrays.equals(x, expected) && Arrays.equals(y, expected) && Arrays.equals(z, expected);            System.out.println(ok + " " + Arrays.toString(expected));        }    }}

true [1, 2, 3, 4, 5, 6]true []true [7]true [3, 3, 3, 3]true [-5, -5, 0, 8, 10]true [1, 2, 3, 4, 5]true [1, 2, 3, 4, 5, 6, 7, 8, 9]true [-2147483648, 0, 2147483647]

All three sorts agree with Java's built-in Arrays.sort on every test, including empty, single, all-equal, negative, already sorted, reversed, and extreme values. Comparing your own implementation against the library on a set of tricky inputs is a very good habit.

Notice temp[j] < temp[i] in the merge. We compare the values directly, not by subtraction, so no overflow (the last test includes Integer.MIN_VALUE and Integer.MAX_VALUE).

In practice you use the library:

• Arrays.sort(int[]) sorts primitives. It uses a tuned dual-pivot quick sort. Stability does not matter for primitives, since equal numbers are indistinguishable.
• Arrays.sort(T[], comparator), list.sort(comparator) and Collections.sort(list) sort objects. They use TimSort, a stable merge-based algorithm that is very fast on partly-ordered data.
• You cannot pass a comparator to Arrays.sort(int[]). To sort numbers in descending order, either sort ascending and reverse, or use Integer[] with Collections.reverseOrder().

The most useful comparator tools:

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Main {    static class Person {        final String name;        final int age;        Person(String name, int age) {            this.name = name;            this.age = age;        }        @Override        public String toString() {            return name + "(" + age + ")";        }    }    public static void main(String[] args) {        Integer[] boxed = {5, 2, 9, 1};        Arrays.sort(boxed, Collections.reverseOrder());        System.out.println(Arrays.toString(boxed));        String[] words = {"pear", "fig", "apple", "kiwi", "date"};        Arrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));        System.out.println(Arrays.toString(words));        int[][] intervals = {{5, 8}, {1, 3}, {2, 6}, {1, 2}};        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));        System.out.println(Arrays.deepToString(intervals));        List<Person> people = new ArrayList<>(List.of(                new Person("Asha", 30), new Person("Ravi", 25), new Person("Meena", 30), new Person("Kiran", 25)));        people.sort(Comparator.comparingInt(p -> p.age));     // stable: equal ages keep their original order        System.out.println(people);    }}

[9, 5, 2, 1][fig, date, kiwi, pear, apple][[1, 2], [1, 3], [2, 6], [5, 8]][Ravi(25), Kiran(25), Asha(30), Meena(30)]

Look at the last line. Ravi came before Kiran in the input, and both are 25, so a stable sort keeps them in that order, and likewise Asha stays before Meena. If an interviewer asks "is this sort stable?", this is what they mean.

• Binary search on unsorted data. It returns garbage with no error.
• Mixing interval conventions, for example hi = a.length - 1 with while (lo < hi), or hi = mid with lo <= hi. Pick closed or half-open and stay with it.
• Infinite loops. If a branch sets lo = mid or hi = mid and the interval can stop shrinking, the loop never ends. In the closed form, always use mid + 1 and mid - 1.
• Overflow in (lo + hi) / 2 and in mid * mid. Use lo + (hi - lo) / 2 and long for products.
• Empty and single-element arrays. Test them for every search and sort.
• Duplicates. Decide which occurrence you want, and use lower or upper bound.
• Forgetting that Arrays.sort(int[]) mutates the array. Copy first if you need the original.
• Subtraction comparators, and comparators that are not consistent.
• Sorting when you only need the top k or just the minimum. A heap or a single pass is cheaper.
• Relying on the stability of Arrays.sort(int[]) or assuming quick sort is stable. Only the object sorts are stable.

static int searchBuggy(int[] a, int target) {    int lo = 0;    int hi = a.length - 1;    while (lo <= hi) {        int mid = (lo + hi) / 2;        if (a[mid] == target) {            return mid;        }        if (a[mid] < target) {            lo = mid;        } else {            hi = mid;        }    }    return -1;}

// File: Main.javaimport java.util.Arrays;public class Main {    static int lowerBound(int[] a, int target) {        int lo = 0;        int hi = a.length;        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] < target) {                lo = mid + 1;            } else {                hi = mid;            }        }        return lo;    }    static int upperBound(int[] a, int target) {        int lo = 0;        int hi = a.length;        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] <= target) {                lo = mid + 1;            } else {                hi = mid;            }        }        return lo;    }    static int[] firstAndLast(int[] a, int target) {        int first = lowerBound(a, target);        if (first == a.length || a[first] != target) {            return new int[] {-1, -1};        }        return new int[] {first, upperBound(a, target) - 1};    }    public static void main(String[] args) {        System.out.println(Arrays.toString(firstAndLast(new int[] {5, 7, 7, 8, 8, 10}, 8)));        System.out.println(Arrays.toString(firstAndLast(new int[] {5, 7, 7, 8, 8, 10}, 6)));        System.out.println(Arrays.toString(firstAndLast(new int[] {}, 0)));        System.out.println(Arrays.toString(firstAndLast(new int[] {2, 2, 2}, 2)));        System.out.println(Arrays.toString(firstAndLast(new int[] {1, 3}, 5)));    }}

[3, 4][-1, -1][-1, -1][0, 2][-1, -1]

// File: Main.javapublic class Main {    static int searchInsert(int[] a, int target) {        int lo = 0;        int hi = a.length;        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] < target) {                lo = mid + 1;            } else {                hi = mid;            }        }        return lo;    }    public static void main(String[] args) {        int[] a = {1, 3, 5, 6};        System.out.println(searchInsert(a, 5) + " " + searchInsert(a, 2) + " " + searchInsert(a, 7) + " " + searchInsert(a, 0));        System.out.println(searchInsert(new int[] {}, 4));    }}

2 1 4 00

// File: Main.javapublic class Main {    static String searchBuggy(int[] a, int target) {        int lo = 0;        int hi = a.length - 1;        int iterations = 0;        while (lo <= hi) {            if (++iterations > 1000) {                return "gave up after 1000 iterations (infinite loop)";            }            int mid = (lo + hi) / 2;            if (a[mid] == target) {                return "found at " + mid;            }            if (a[mid] < target) {                lo = mid;            } else {                hi = mid;            }        }        return "not found";    }    static int searchFixed(int[] a, int target) {        int lo = 0;        int hi = a.length - 1;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            if (a[mid] == target) {                return mid;            }            if (a[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return -1;    }    public static void main(String[] args) {        System.out.println(searchBuggy(new int[] {1, 3}, 2));        System.out.println(searchFixed(new int[] {1, 3}, 2));        System.out.println(searchFixed(new int[] {1, 3}, 3));    }}

gave up after 1000 iterations (infinite loop)-11

// File: Main.javapublic class Main {    static boolean canShip(int[] weights, int days, long capacity) {        int daysUsed = 1;        long load = 0;        for (int w : weights) {            if (load + w > capacity) {      // this package does not fit, start a new day                daysUsed++;                load = 0;            }            load += w;        }        return daysUsed <= days;    }    static long shipCapacity(int[] weights, int days) {        long lo = 0;        long hi = 0;        for (int w : weights) {            lo = Math.max(lo, w);            hi += w;        }        while (lo < hi) {            long mid = lo + (hi - lo) / 2;            if (canShip(weights, days, mid)) {                hi = mid;                   // mid works, so try smaller            } else {                lo = mid + 1;               // mid is too small            }        }        return lo;    }    public static void main(String[] args) {        System.out.println(shipCapacity(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5));        System.out.println(shipCapacity(new int[] {3, 2, 2, 4, 1, 4}, 3));        System.out.println(shipCapacity(new int[] {1, 2, 3, 1, 1}, 4));        System.out.println(shipCapacity(new int[] {7}, 1));        System.out.println(shipCapacity(new int[] {5, 5, 5}, 3));    }}

156375

• Next: Two Pointers: Solve Problems by Coordinating Indices uses sortedness in another way, to find pairs without nested loops.
• Related: the merge step here is the one from Arrays. Intervals, which you will sort by start, are the focus of Greedy Algorithms and Interval Problems. Priority queues from the heap article are the right tool when you only need the top k and not a full sort.
• Practice habit: when you write a binary search, write down your interval convention and the invariant as a comment before the loop.