Linear and Binary Search

Every day, programs find one thing among thousands: your record in the enrollment system, a name in your phone's contacts, a product from its barcode. The steps a program follows to find it are called a search algorithm.

Picture two ways to find a classmate named Mia:

Here are the words that come with searching:

Why -1? It can never be a real index (indexes start at 0), so nobody can mistake it for a position.

This lesson teaches the two basic searches. Linear search checks one value after another, like the pile. Binary search keeps checking the middle and throwing away half, like the class list. You already played binary search: it is the guessing game from the Introduction .

By hand, it follows four steps:

1. Start at index 0.
2. Check the value there. If it equals the target: found. Give back this index and stop.
3. If not, move to the next index and go back to step 2.
4. If there are no values left: not found. Give back -1.

In Java, it is a loop with an early return. Step through it on a small array in no order, looking for 93:

 1static int linearSearch(int[] arr, int target) { 2  for (int i = 0; i < arr.length; i++) { 3    if (arr[i] == target) { 4      return i;         // found: give back its index 5    } 6  } 7  return -1;            // checked them all: not found 8}

Here is how to read the important lines aloud:

for (int i = 0; i < arr.length; i++) {
  if (arr[i] == target) {
    return i;
  } else {
    return -1;        // gives up too early!
  }
}
return -1;

Linear search never uses the order of the values. When the values are sorted (in order, smallest to largest), one check can tell us much more: if the middle value is too small, everything to its left is too small too.

Three numbers keep track of the part that is still possible:

"Rounded down" is just how Java divides two ints : (0 + 11) / 2 is 5, not 5.5.

The steps, by hand:

1. Set low = 0 and high = the last index.
2. While low ≤ high: find mid and check the value there.
   • Equal to the target: found. Give back mid.
   • Smaller than the target: the target is to the right. Set low = mid + 1.
   • Bigger than the target: the target is to the left. Set high = mid - 1.
3. If low passes high, nothing is left: not found. Give back -1.

On paper (and on exams), write one row per check:

4 checks. Linear search would have needed 10 (indexes 0 to 9).

Run both searches on the same sorted array and count the checks. Try 71, then 4 (the first value: which search wins now?), then 88, then a number that is not there.

Each step of the by-hand rule becomes one or two lines. Step through it looking for 20, which is not in the array, to see how the method knows when to stop:

 1static int binarySearch(int[] arr, int target) { 2  int low = 0; 3  int high = arr.length - 1; 4  while (low <= high) { 5    int mid = (low + high) / 2; 6    if (arr[mid] == target) { 7      return mid;              // found 8    } else if (arr[mid] < target) { 9      low = mid + 1;           // target is to the right10    } else {11      high = mid - 1;          // target is to the left12    }13  }14  return -1;                   // nothing left: not found15}

Here is how to read the key lines aloud:

 1public class Main {
 2  static int linearSearch(int[] arr, int target) {
 3    for (int i = 0; i < arr.length; i++) {
 4      if (arr[i] == target) {
 5        return i;
 6      }
 7    }
 8    return -1;
 9  }
10
11  static int binarySearch(int[] arr, int target) {
12    int low = 0;
13    int high = arr.length - 1;
14    while (low <= high) {
15      int mid = (low + high) / 2;
16      if (arr[mid] == target) {
17        return mid;
18      } else if (arr[mid] < target) {
19        low = mid + 1;
20      } else {
21        high = mid - 1;
22      }
23    }
24    return -1;
25  }
26
27  public static void main(String[] args) {
28    int[] pile = {42, 17, 8, 93, 25, 61};
29    System.out.println(linearSearch(pile, 93));   // 3
30    System.out.println(linearSearch(pile, 50));   // -1
31
32    int[] sorted = {4, 9, 15, 21, 27, 34, 42, 56, 63, 71, 80, 88};
33    System.out.println(binarySearch(sorted, 71)); // 9
34    System.out.println(binarySearch(sorted, 20)); // -1
35  }
36}

Count the checks in the worst case (the target is not there):

Look at the binary column: every time the number of values doubles, binary search needs only one more check. Linear search needs twice as many.

So is binary search always better? No. It has two conditions:

1. The values must be sorted. Sorting takes work too (that is what the sorting lessons are about). If a list is searched only once, sorting it first can cost more than a simple linear search.
2. It needs to jump to the middle in one step, which an array can do but a linked list cannot (see access ).

Here is how to choose:

Good to know: books describe this growth with short names. Linear search is O(n) ("order n": the work grows with the number of values). Binary search is O(log n) ("order log n": the work grows with how many times you can halve n). You will see these names again when the course analyzes algorithms.

In real programs, you rarely write binary search yourself: Java already has it. Arrays.sort puts an array in order, and Arrays.binarySearch searches it. Both live in java.util.Arrays, so the file starts with an import line that tells Java where to find them.

 1import java.util.Arrays;
 2
 3public class Main {
 4  public static void main(String[] args) {
 5    int[] arr = {56, 4, 88, 21, 71, 9};
 6    Arrays.sort(arr);                                 // put it in order first
 7    System.out.println(Arrays.toString(arr));         // [4, 9, 21, 56, 71, 88]
 8    System.out.println(Arrays.binarySearch(arr, 71)); // 4
 9    System.out.println(Arrays.binarySearch(arr, 20)); // -3 (negative: not found)
10  }
11}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Two things to notice:

• Arrays.binarySearch also needs a sorted array. On an unsorted array, its answer cannot be trusted (like the unsorted-data mistake in Part 3 ).
• When the target is missing, it gives back a negative number, but not always -1 (here, -3). Check for "less than 0", not "equal to -1".

Not graded. Tap an answer to see if you got it, and read why.

Next lesson: Basic sorting. Binary search needs sorted values, so next you learn how to sort them. (A binary search tree, from the midterm, uses the same halving idea without needing a sorted array.)