Arrays and binary search: big-O notation, ArrayList and Arrays.binarySearch

← Back to the section

An array is the simplest data structure there is: numbered slots lying next to each other in memory. It is a good place to start, because all the main trade-offs show up on it at once — some things an array does instantly, others slowly. It is also the easiest place to see how the speed of an algorithm is measured at all, through big-O notation. If you have not read the introduction to the section yet, the common terms live there.

What an array can do and what it cannot

An array has one superpower: access by index in a single step. If the element you need lives in slot 5, the program takes it immediately without walking the others — the address of the slot is computed from the index directly.

The other operations are harder:

• Insert at the end is fast: drop the value into the first free slot.
• Search by value is slow: when the index is unknown, the slots have to be checked one after another.
• Delete is slow: once an element is removed a "hole" is left behind, and the elements after it have to be shifted to close it.

A plain array also has a fixed size: as many slots as you allocated, that is all you get.

A sorted array

An array can be kept sorted: the smallest value in slot 0, then upwards. You pay for it on insert — a new element cannot simply be dropped at the end, you have to find its place and shift everyone larger. In exchange you get a radically faster search.

Linear search

The simplest way to find an element is a linear search: start at the beginning and compare every slot with the value you want, until you find it or run out of slots. In a sorted array there is a small bonus: as soon as you meet a value greater than the one you are looking for, searching further is pointless — you can stop. But on average you still check half of the array. On a million elements that is up to half a million comparisons — slow.

Binary search

In a sorted array a far faster binary search works. Its logic is the children's guessing game: one player picks a number from 1 to 100, the other guesses, and the first one answers "higher" or "lower".

How do you guess in the fewest attempts? Name the middle of the remaining range. The first question is 50. "Lower" → the number is in 1–49, the next question is 25. "Higher" → the range is 26–49, next is 37. Every attempt halves the range, so a number from 1 to 100 is guessed in at most 7 attempts instead of 100.

Binary search does exactly that to an array: keep the bounds of the range where the element may lie, look at the middle element and, comparing it with the key, throw away one half. The steps counter counts the comparisons, so you can see what the search cost:

live example

public class BinarySearchDemo {
    static int steps = 0;

    static int binarySearch(int[] a, int key) {
        int lower = 0;
        int upper = a.length - 1;
        while (lower <= upper) {
            steps++;
            int mid = (lower + upper) >>> 1;
            if (a[mid] == key) return mid;
            if (a[mid] < key) lower = mid + 1;
            else upper = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 11, 18, 23, 29, 34, 41, 52, 63, 70};
        int found = binarySearch(a, 63);
        System.out.println("63 sits in slot " + found);
        System.out.println("comparisons: " + steps + ", slots in the array: " + a.length);
    }
}

One detail in this code deserves an explanation: why the middle is computed as (lower + upper) >>> 1 and not by the usual division by two. While the array is small there is no difference. But if it is huge and both indexes approach two billion, their sum no longer fits into an int and turns negative — and then the program reaches for a negative index and crashes. The >>> operator shifts the bits to the right, that is, divides by two, but it does so without a sign, and the overflow does not bother it. This bug lived in the Java standard library for almost ten years before it was found, so falling for it is nothing to be ashamed of.

Every pass of the loop cuts off half of the remaining elements. That is why a search over 100 elements takes about 7 comparisons, over 1000 about 10, over a million about 20. Compare that with a linear search: 500,000 against 20 on a million. The difference is enormous, and it is the whole point of keeping an array sorted.

The trade-off of a sorted array

So a sorted array pays for its fast search with a slow insert (elements have to be shifted to make room) and a still slow delete. The practical conclusion:

• a sorted array is good when searching happens often and inserts and deletes are rare. An employee directory is the example: it is read and searched all the time, while people are hired and let go rarely;
• a sorted array is bad when inserts and deletes come in a stream. A warehouse ledger is the example: goods arrive and leave every minute.

This is the first instance of the main principle of the section: you choose a structure by which operations are frequent in your case.

Logarithms and big-O notation

We said "about 20 comparisons on a million". Where does that number come from? Binary search halves the range until a single element is left, and the number of halvings that turn N into 1 is the base-2 logarithm of N. For a million, log₂(1,000,000) ≈ 20. A logarithm grows very slowly: the data grew a thousand times over, the number of steps only two or three times.

To talk about speed without tying yourself to a particular machine and without counting seconds, people use big-O notation. It describes how the number of operations grows as the amount of data N grows, throwing away everything inessential. Three cases have already come up:

• O(1) — constant time. The number of steps does not depend on N. That is an append to an unsorted array and an access by index: ten elements or a million, it is one step.
• O(N) — linear time. The number of steps grows in proportion to N. That is a linear search: twice the data, twice the work.
• O(log N) — logarithmic time. The number of steps grows as the logarithm of N, that is, very slowly. That is binary search.

Big-O is read as "order of growth". O(1) is better than O(log N), and O(log N) is much better than O(N) on large data. Constants and small details are dropped: what matters is not "one and a half times faster" but how the algorithm behaves when the data becomes very large.

Why not arrays only

If a sorted array searches so fast, why do we need the other structures at all? Because of that same price: its insert and delete are O(N), and its size is fixed. As soon as a task has many inserts and deletes, an array becomes the bottleneck. Later in the section we meet structures that search almost as fast while inserting and deleting quickly — linked lists, trees, hash tables. They pay for that convenience with a more complicated design.

How it is done in Java

You almost never need to write your own growing array — all of that was settled long ago in the standard library. But you still have to choose a structure, and for that you need to know what is inside it.

The reference implementation of an array in Java is ArrayList. The word "list" in the name is misleading: there are no nodes and no references inside, it is an ordinary array of objects that the class keeps in a field and swaps for a larger one when it runs out of room.

Growth works like this: when the array is full, ArrayList allocates a new one — roughly one and a half times longer — and copies the old elements over. Such a copy costs O(N), but it happens the more rarely the longer the list is. Spread that price over all the additions and every add at the end costs O(1) amortized: almost always one step, occasionally an expensive move.

The rest of the complexity is exactly the array from this article:

• get(i) and set(i, v) — O(1), the address of the slot is computed from the index;
• add(v) at the end — O(1) amortized;
• add(i, v) and remove(i) in the middle — O(N): the neighbours have to be shifted. It is System.arraycopy that does it — a fast memory copy, but the work is still linear;
• contains and indexOf — O(N), that is the very same linear search.

You do not need to write binary search by hand either: for a sorted array there is Arrays.binarySearch, for a sorted list Collections.binarySearch. Inside they run the same loop halving the range, including the safe >>> shift instead of a division by two.

There is one trap here, and it is a nasty one: binarySearch does not check whether the data is sorted. On an unordered array it will not crash and will not complain — it simply returns a wrong answer. And the return value has to be read carefully: when the element is not found, the method gives back not -1 but a negative number encoding the position for an insert — -(position) - 1. All three cases at once:

live example

import java.util.Arrays;

public class JdkBinarySearch {
    public static void main(String[] args) {
        int[] sorted = {3, 7, 11, 18, 23};
        System.out.println("11 -> " + Arrays.binarySearch(sorted, 11));
        System.out.println("12 -> " + Arrays.binarySearch(sorted, 12));

        int[] unsorted = {23, 3, 18, 7, 11};
        System.out.println("11 in an unsorted array -> " + Arrays.binarySearch(unsorted, 11));
    }
}

The first line is an honest hit in slot 2. The second: there is no 12, and -4 reads as "insert at position 3". The third is the trap: 11 is in the array, but the array is not sorted, and the method quietly answers "not found".

In short

• An array takes an element by index instantly (O(1)), but searches by value and deletes slowly (O(N)).
• A sorted array allows a binary search — halving the range, O(log N): about 20 steps on a million elements instead of half a million.
• It pays for that with a slow insert: elements have to be shifted. It is good when the search is frequent and inserts and deletes are rare.
• Big-O notation describes how the number of operations grows with the amount of data: O(1) constant, O(log N) very slow growth, O(N) proportional. It is the common yardstick for the whole section.
• In Java the array from this article is ArrayList: get/set in O(1), add at the end in O(1) amortized (growth roughly one and a half times), insert and delete in the middle in O(N).
• Arrays.binarySearch does not check the ordering and quietly lies on unsorted data; "not found" comes back as -(insertion point) - 1, not as -1.

What to read next

• Math behind big O — where logarithms come from and why log₂ N is the number of halvings.
• Simple sorting — three ways to put an array in order, without which binary search does not work.
• Linked lists — the structure with the opposite trade-off: insert in O(1), but search only by walking.
• Binary search on the answer — the same trick applied to a range of values instead of an array.