Binary Search - Java Programming

When looking up a word in a dictionary or finding a contact in an alphabetically sorted phone book, you can jump to the middle and decide which half to search next. Binary search formalizes that idea for sorted arrays.

Basic Implementation

                            Basic.java
                        
Replay: real traced execution (multi-file project)

                            public class Basic {
    static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;

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

        return -1;  // not found
    }

    public static void main(String[] args) {
        int[] sorted = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

        System.out.println("Array: " + java.util.Arrays.toString(sorted));
        System.out.println("Search 7: index " + binarySearch(sorted, 7));
        System.out.println("Search 1: index " + binarySearch(sorted, 1));
        System.out.println("Search 19: index " + binarySearch(sorted, 19));
        System.out.println("Search 10: index " + binarySearch(sorted, 10));
    }
}

                        
1public static void main(String[] args)⋯20public static void main(String[] args) {21    int[] sorted = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};2223    System.out.println("Array: " + java.util.Arrays.toString(sorted));24    System.out.println("Search 7: index " + binarySearch(sorted, 7));25    System.out.println("Search 1: index " + binarySearch(sorted, 1));⋯outputArray: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
2low ← 0, high ← 9pass 1 of 41public class Basic {2    static int binarySearch(int[] arr, int target7) {3        int low→ 0 = 0;4        int high→ 9 = arr.length10 - 1;5        while (low <= high) {⋯All 4 passes — pass 1 is the card abovepasstargetlowhigh
1709
2109
31909
41009
3mid ← 4pass 1 of 14⋯4int high = arr.length - 1;5while (low0 <= high9) {6    int mid→ 4 = (low0 + high9) / 2;⋯14 passes — pass 1 is the card abovepasslowhighmid
1094
2031
3232
4333
5094
6031
7000
8094
9597
⋯ 3 more passes ⋯
13597
14565
4high ← 3pass 1 of 5⋯11    low = mid + 1;  // search right half12} else {13    high→ 3 = mid4 - 1;  // search left half14}⋯All 5 passes — pass 1 is the card abovepassmidhigh
143
243
310
476
554
5low ← 2pass 1 of 6⋯9    return mid;  // found10} else if (arr[mid]3 < target7) {11    low→ 2 = mid1 + 1;  // search right half12} else {⋯All 6 passes — pass 1 is the card abovepassarr[mid]midtargetlow
13172
25273
394195
4157198
5178199
694105
6if (arr[mid] == target)pass 1 of 3⋯8if (arr[mid]7 == target7) {9    return mid3;  // found10} else if (arr[mid] < target) {⋯All 3 passes — pass 1 is the card abovepassarr[mid]midtarget
1737
2101
319919
7System.out.println("Search 7: index " + binarySearch(sorted, 7));⋯23System.out.println("Array: " + java.util.Arrays.toString(sorted));24System.out.println("Search 7: index " + binarySearch(sorted, 7));25System.out.println("Search 1: index " + binarySearch(sorted, 1));26System.out.println("Search 19: index " + binarySearch(sorted, 19));⋯outputSearch 7: index 3
8System.out.println("Search 1: index " + binarySearch(sorted, 1));⋯24System.out.println("Search 7: index " + binarySearch(sorted, 7));25System.out.println("Search 1: index " + binarySearch(sorted, 1));26System.out.println("Search 19: index " + binarySearch(sorted, 19));27System.out.println("Search 10: index " + binarySearch(sorted, 10));⋯outputSearch 1: index 0
9System.out.println("Search 19: index " + binarySearch(sorted, 19));⋯25    System.out.println("Search 1: index " + binarySearch(sorted, 1));26    System.out.println("Search 19: index " + binarySearch(sorted, 19));27    System.out.println("Search 10: index " + binarySearch(sorted, 10));28}⋯outputSearch 19: index 9
10return -1;  // not found⋯17    return -1;  // not found18}⋯
11System.out.println("Search 10: index " + binarySearch(sorted, 10));⋯26    System.out.println("Search 19: index " + binarySearch(sorted, 19));27    System.out.println("Search 10: index " + binarySearch(sorted, 10));28}⋯outputSearch 10: index -1

All 4 passes — pass 1 is the card above
pass	`target`	`high`
1	7	9
2	1	9
3	19	9
4	10	9

14 passes — pass 1 is the card above
pass	`low`	`high`	`mid`
1	0	9	4
2	0	3	1
3	2	3	2
4	3	3	3
5	0	9	4
6	0	3	1
7	0	0	0
8	0	9	4
9	5	9	7
⋯ 3 more passes ⋯
13	5	9	7
14	5	6	5

All 5 passes — pass 1 is the card above
pass	`mid`	`high`
1	4	3
2	4	3
3	1	0
4	7	6
5	5	4

All 6 passes — pass 1 is the card above
pass	`arr[mid]`	`mid`	`target`	`low`
1	3	1	7	2
2	5	2	7	3
3	9	4	19	5
4	15	7	19	8
5	17	8	19	9
6	9	4	10	5

All 3 passes — pass 1 is the card above
pass	`arr[mid]`	`mid`	`target`
1	7	3	7
2	1	0	1
3	19	9	19

Binary Search A divide-and-conquer search algorithm that halves the search space with each comparison. It requires sorted data and runs in O(log n) time.

Tracing the Algorithm

The low, mid, and high boundaries show how each comparison removes half of the remaining search area.

                            target
                            target = 70 (default)target = 10target = 25
                        

                            Trace.java
                        
Replay: real traced execution (multi-file project)

                            public class Trace {
    static int binarySearchTrace(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int iteration = 0;
        while (low <= high) {
            iteration++;
            int mid = (low + high) / 2;

            System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",
                            iteration, low, mid, high, arr[mid]);

            if (arr[mid] == target) {
                System.out.println("Found at index " + mid);
                return mid;
            } else if (arr[mid] < target) {
                System.out.println("  Target > mid, search right");
                low = mid + 1;
            } else {
                System.out.println("  Target < mid, search left");
                high = mid - 1;
            }
        }

        System.out.println("Not found");
        return -1;
    }

    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int target = 70;

        System.out.println("Searching for " + target + ":");
        binarySearchTrace(sorted, target);
    }
}
public class Trace {
    static int binarySearchTrace(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int iteration = 0;
        while (low <= high) {
            iteration++;
            int mid = (low + high) / 2;

            System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",
                            iteration, low, mid, high, arr[mid]);

            if (arr[mid] == target) {
                System.out.println("Found at index " + mid);
                return mid;
            } else if (arr[mid] < target) {
                System.out.println("  Target > mid, search right");
                low = mid + 1;
            } else {
                System.out.println("  Target < mid, search left");
                high = mid - 1;
            }
        }

        System.out.println("Not found");
        return -1;
    }

    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int target = 10;

        System.out.println("Searching for " + target + ":");
        binarySearchTrace(sorted, target);
    }
}
public class Trace {
    static int binarySearchTrace(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int iteration = 0;
        while (low <= high) {
            iteration++;
            int mid = (low + high) / 2;

            System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",
                            iteration, low, mid, high, arr[mid]);

            if (arr[mid] == target) {
                System.out.println("Found at index " + mid);
                return mid;
            } else if (arr[mid] < target) {
                System.out.println("  Target > mid, search right");
                low = mid + 1;
            } else {
                System.out.println("  Target < mid, search left");
                high = mid - 1;
            }
        }

        System.out.println("Not found");
        return -1;
    }

    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int target = 25;

        System.out.println("Searching for " + target + ":");
        binarySearchTrace(sorted, target);
    }
}

                        
1target ← 70⋯29public static void main(String[] args) {30    int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};31    int target→ 70 = 70; //@target=70, 25, 103233    System.out.println("Searching for " + target70 + ":");34    binarySearchTrace(sorted, target70);35}⋯outputSearching for 70:
2low ← 0, high ← 8, iteration ← 01public class Trace {2    static int binarySearchTrace(int[] arr, int target70) {3        int low→ 0 = 0;4        int high→ 8 = arr.length9 - 1;5        int iteration→ 0 = 0;6        while (low <= high) {⋯
3iteration ← 1, mid ← 4pass 1 of 2⋯5int iteration = 0;6while (low0 <= high8) {7    iteration→ 1++;8    int mid→ 4 = (low0 + high8) / 2;910    System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",11                    iteration1, low0, mid4, high8, arr[mid]50);⋯
4low ← 5⋯15    return mid;16} else if (arr[mid]50 < target70) {17    System.out.println("  Target > mid, search right");18    low→ 5 = mid4 + 1;19} else {⋯output  Target > mid, search right
5iteration ← 2, mid ← 6pass 2 of 2⋯5int iteration = 0;6while (low5 <= high8) {7    iteration→ 2++;8    int mid→ 6 = (low5 + high8) / 2;910    System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",11                    iteration2, low5, mid6, high8, arr[mid]70);⋯
6if (arr[mid] == target)⋯13if (arr[mid]70 == target70) {14    System.out.println("Found at index " + mid6);15    return mid6;16} else if (arr[mid] < target) {⋯outputFound at index 6
7binarySearchTrace(sorted, target);⋯33    System.out.println("Searching for " + target + ":");34    binarySearchTrace(sorted, target70);35}⋯
1target ← 10⋯29public static void main(String[] args) {30    int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};31    int target→ 10 = 10;3233    System.out.println("Searching for " + target10 + ":");34    binarySearchTrace(sorted, target10);35}⋯outputSearching for 10:
2low ← 0, high ← 8, iteration ← 01public class Trace {2    static int binarySearchTrace(int[] arr, int target10) {3        int low→ 0 = 0;4        int high→ 8 = arr.length9 - 1;5        int iteration→ 0 = 0;6        while (low <= high) {⋯
3iteration ← 1, mid ← 4pass 1 of 3⋯5int iteration = 0;6while (low0 <= high8) {7    iteration→ 1++;8    int mid→ 4 = (low0 + high8) / 2;910    System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",11                    iteration1, low0, mid4, high8, arr[mid]50);⋯All 3 passes — pass 1 is the card abovepassarr[mid]targetiterationmidhigh
150—0 → 143
220—1 → 210
310102 → 300
4high ← 3pass 1 of 2⋯18    low = mid + 1;19} else {20    System.out.println("  Target < mid, search left");21    high→ 3 = mid4 - 1;22}⋯output  Target < mid, search left
5high ← 0pass 2 of 2⋯18    low = mid + 1;19} else {20    System.out.println("  Target < mid, search left");21    high→ 0 = mid1 - 1;22}⋯output  Target < mid, search left
6if (arr[mid] == target)⋯13if (arr[mid]10 == target10) {14    System.out.println("Found at index " + mid0);15    return mid0;16} else if (arr[mid] < target) {⋯outputFound at index 0
7binarySearchTrace(sorted, target);⋯33    System.out.println("Searching for " + target + ":");34    binarySearchTrace(sorted, target10);35}⋯
1target ← 25⋯29public static void main(String[] args) {30    int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90};31    int target→ 25 = 25;3233    System.out.println("Searching for " + target25 + ":");34    binarySearchTrace(sorted, target25);35}⋯outputSearching for 25:
2low ← 0, high ← 8, iteration ← 01public class Trace {2    static int binarySearchTrace(int[] arr, int target25) {3        int low→ 0 = 0;4        int high→ 8 = arr.length9 - 1;5        int iteration→ 0 = 0;6        while (low <= high) {⋯
3iteration ← 1, mid ← 4pass 1 of 3⋯5int iteration = 0;6while (low0 <= high8) {7    iteration→ 1++;8    int mid→ 4 = (low0 + high8) / 2;910    System.out.printf("Iter %d: low=%d, mid=%d, high=%d, arr[mid]=%d%n",11                    iteration1, low0, mid4, high8, arr[mid]50);⋯All 3 passes — pass 1 is the card abovepassarr[mid]targetiterationmidhighlow
150—0 → 1430
220251 → 2132
330—2 → 3212
4high ← 3pass 1 of 2⋯18    low = mid + 1;19} else {20    System.out.println("  Target < mid, search left");21    high→ 3 = mid4 - 1;22}⋯output  Target < mid, search left
5low ← 2⋯15    return mid;16} else if (arr[mid]20 < target25) {17    System.out.println("  Target > mid, search right");18    low→ 2 = mid1 + 1;19} else {⋯output  Target > mid, search right
6high ← 1pass 2 of 2⋯18    low = mid + 1;19} else {20    System.out.println("  Target < mid, search left");21    high→ 1 = mid2 - 1;22}⋯output  Target < mid, search left
7System.out.println("Not found");⋯25    System.out.println("Not found");26    return -1;27}⋯outputNot found
8binarySearchTrace(sorted, target);⋯33    System.out.println("Searching for " + target + ":");34    binarySearchTrace(sorted, target25);35}⋯

All 3 passes — pass 1 is the card above
pass	`arr[mid]`	`target`	`iteration`	`mid`	`high`
1	50	—	0 → 1	4	3
2	20	—	1 → 2	1	0
3	10	10	2 → 3	0	0

All 3 passes — pass 1 is the card above
pass	`arr[mid]`	`target`	`iteration`	`mid`	`high`	`low`
1	50	—	0 → 1	4	3	0
2	20	25	1 → 2	1	3	2
3	30	—	2 → 3	2	1	2

Recursive Version

Binary search can also be expressed recursively by searching either the left half or the right half.

                            Recursive.java
                        
Replay: real traced execution (multi-file project)

                            public class Recursive {
    static int binarySearchRecursive(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1;  // not found
        }
        int mid = (low + high) / 2;

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

    static int binarySearch(int[] arr, int target) {
        return binarySearchRecursive(arr, target, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] sorted = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};

        System.out.println("Array: " + java.util.Arrays.toString(sorted));
        System.out.println("Search 23: index " + binarySearch(sorted, 23));
        System.out.println("Search 2: index " + binarySearch(sorted, 2));
        System.out.println("Search 100: index " + binarySearch(sorted, 100));
    }
}

                        
1public static void main(String[] args)⋯21public static void main(String[] args) {22    int[] sorted = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};2324    System.out.println("Array: " + java.util.Arrays.toString(sorted));25    System.out.println("Search 23: index " + binarySearch(sorted, 23));26    System.out.println("Search 2: index " + binarySearch(sorted, 2));⋯outputArray: [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
2static int binarySearch(int[] arr, int target)pass 1 of 3⋯17static int binarySearch(int[] arr, int target23) {18    return binarySearchRecursive(arr, target23, 0, arr.length11 - 1);19}⋯All 3 passes — pass 1 is the card abovepasstargetarr[mid]midlowhigh
123235——
22250—
3100——1110
3mid ← 5pass 1 of 91public class Recursive {2    static int binarySearchRecursive(int[] arr, int target23, int low0, int high10) {3        if (low > high) {4            return -1;  // not found5        }6        int mid→ 5 = (low0 + high10) / 2;⋯All 9 passes — pass 1 is the card abovepasstargetlowhigharr[mid]mid
123010235
22010—5
3204—2
420120
5100010—5
6100610—8
7100910—9
81001010—10
91001110——
4if (arr[mid] == target)pass 1 of 2⋯8if (arr[mid]23 == target23) {9    return mid5;  // found10} else if (arr[mid] < target) {⋯
5System.out.println("Search 23: index " + binarySearch(sorted, 23));⋯24System.out.println("Array: " + java.util.Arrays.toString(sorted));25System.out.println("Search 23: index " + binarySearch(sorted, 23));26System.out.println("Search 2: index " + binarySearch(sorted, 2));27System.out.println("Search 100: index " + binarySearch(sorted, 100));⋯outputSearch 23: index 5
6elsepass 1 of 2⋯11    return binarySearchRecursive(arr, target, mid + 1, high);  // right12} else {13    return binarySearchRecursive(arr, target2, low0, mid5 - 1);  // left14}⋯
7elsepass 2 of 2⋯11    return binarySearchRecursive(arr, target, mid + 1, high);  // right12} else {13    return binarySearchRecursive(arr, target2, low0, mid2 - 1);  // left14}⋯
8if (arr[mid] == target)pass 2 of 2⋯8if (arr[mid]2 == target2) {9    return mid0;  // found10} else if (arr[mid] < target) {⋯
9System.out.println("Search 2: index " + binarySearch(sorted, 2));⋯25    System.out.println("Search 23: index " + binarySearch(sorted, 23));26    System.out.println("Search 2: index " + binarySearch(sorted, 2));27    System.out.println("Search 100: index " + binarySearch(sorted, 100));28}⋯outputSearch 2: index 0
10if (arr[mid] < target)pass 1 of 4⋯9    return mid;  // found10} else if (arr[mid]23 < target100) {11    return binarySearchRecursive(arr, target100, mid5 + 1, high10);  // right12} else {⋯All 4 passes — pass 1 is the card abovepassarr[mid]midlow
1235—
2568—
3679—
4781011
11if (low > high)⋯2static int binarySearchRecursive(int[] arr, int target, int low, int high) {3    if (low11 > high10) {4        return -1;  // not found5    }⋯
12System.out.println("Search 100: index " + binarySearch(sorted, 100));⋯26    System.out.println("Search 2: index " + binarySearch(sorted, 2));27    System.out.println("Search 100: index " + binarySearch(sorted, 100));28}⋯outputSearch 100: index -1

All 3 passes — pass 1 is the card above
pass	`target`	`arr[mid]`	`mid`	`low`	`high`
1	23	23	5	—	—
2	2	2	5	0	—
3	100	—	—	11	10

All 9 passes — pass 1 is the card above
pass	`target`	`low`	`high`	`arr[mid]`	`mid`
1	23	0	10	23	5
2	2	0	10	—	5
3	2	0	4	—	2
4	2	0	1	2	0
5	100	0	10	—	5
6	100	6	10	—	8
7	100	9	10	—	9
8	100	10	10	—	10
9	100	11	10	—	—

All 4 passes — pass 1 is the card above
pass	`arr[mid]`	`mid`	`low`
1	23	5	—
2	56	8	—
3	67	9	—
4	78	10	11

Finding Insertion Points

                            InsertionPoint.java
                        
Replay: real traced execution (multi-file project)

                            public class InsertionPoint {
    static int findInsertionPoint(int[] arr, int value) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;  // insertion point
    }

    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50, 60, 70};

        System.out.println("Array: " + java.util.Arrays.toString(sorted));
        System.out.println("Insert 25 at index: " + findInsertionPoint(sorted, 25));
        System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, 5));
        System.out.println("Insert 75 at index: " + findInsertionPoint(sorted, 75));
        System.out.println("Insert 40 at index: " + findInsertionPoint(sorted, 40));
    }
}

                        
1public static void main(String[] args)⋯18public static void main(String[] args) {19    int[] sorted = {10, 20, 30, 40, 50, 60, 70};2021    System.out.println("Array: " + java.util.Arrays.toString(sorted));22    System.out.println("Insert 25 at index: " + findInsertionPoint(sorted, 25));23    System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, 5));⋯outputArray: [10, 20, 30, 40, 50, 60, 70]
2low ← 0, high ← 6pass 1 of 41public class InsertionPoint {2    static int findInsertionPoint(int[] arr, int value25) {3        int low→ 0 = 0;4        int high→ 6 = arr.length7 - 1;5        while (low <= high) {⋯All 4 passes — pass 1 is the card abovepassvaluelowhigh
12506
2506
37506
44006
3mid ← 3pass 1 of 12⋯4int high = arr.length - 1;5while (low0 <= high6) {6    int mid→ 3 = (low0 + high6) / 2;⋯All 12 passes — pass 1 is the card abovepasslowhighmid
1063
2021
3222
4063
5021
6000
7063
8465
9666
10063
11021
12222
4high ← 2pass 1 of 6⋯9    low = mid + 1;10} else {11    high→ 2 = mid3 - 1;12}⋯All 6 passes — pass 1 is the card abovepassmidhigh
132
221
332
410
50-1
632
5low ← 2pass 1 of 6⋯8if (arr[mid]20 < value25) {9    low→ 2 = mid1 + 1;10} else {⋯All 6 passes — pass 1 is the card abovepassarr[mid]midvaluelow
1201252
2403754
3605756
4706757
5201402
6302403
6return low;  // insertion point⋯15    return low2;  // insertion point16}⋯
7System.out.println("Insert 25 at index: " + findInsertionPoint(sorted,…⋯21System.out.println("Array: " + java.util.Arrays.toString(sorted));22System.out.println("Insert 25 at index: " + findInsertionPoint(sorted, 25));23System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, 5));24System.out.println("Insert 75 at index: " + findInsertionPoint(sorted, 75));⋯outputInsert 25 at index: 2
8return low;  // insertion point⋯15    return low0;  // insertion point16}⋯
9System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, …⋯22System.out.println("Insert 25 at index: " + findInsertionPoint(sorted, 25));23System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, 5));24System.out.println("Insert 75 at index: " + findInsertionPoint(sorted, 75));25System.out.println("Insert 40 at index: " + findInsertionPoint(sorted, 40));⋯outputInsert 5 at index: 0
10return low;  // insertion point⋯15    return low7;  // insertion point16}⋯
11System.out.println("Insert 75 at index: " + findInsertionPoint(sorted,…⋯23    System.out.println("Insert 5 at index: " + findInsertionPoint(sorted, 5));24    System.out.println("Insert 75 at index: " + findInsertionPoint(sorted, 75));25    System.out.println("Insert 40 at index: " + findInsertionPoint(sorted, 40));26}⋯outputInsert 75 at index: 7
12return low;  // insertion point⋯15    return low3;  // insertion point16}⋯
13System.out.println("Insert 40 at index: " + findInsertionPoint(sorted,…⋯24    System.out.println("Insert 75 at index: " + findInsertionPoint(sorted, 75));25    System.out.println("Insert 40 at index: " + findInsertionPoint(sorted, 40));26}⋯outputInsert 40 at index: 3

All 4 passes — pass 1 is the card above
pass	`value`	`high`
1	25	6
2	5	6
3	75	6
4	40	6

All 12 passes — pass 1 is the card above
pass	`low`	`high`	`mid`
1	0	6	3
2	0	2	1
3	2	2	2
4	0	6	3
5	0	2	1
6	0	0	0
7	0	6	3
8	4	6	5
9	6	6	6
10	0	6	3
11	0	2	1
12	2	2	2

All 6 passes — pass 1 is the card above
pass	`mid`	`high`
1	3	2
2	2	1
3	3	2
4	1	0
5	0	-1
6	3	2

All 6 passes — pass 1 is the card above
pass	`arr[mid]`	`mid`	`value`	`low`
1	20	1	25	2
2	40	3	75	4
3	60	5	75	6
4	70	6	75	7
5	20	1	40	2
6	30	2	40	3

Insertion Point When a target is not found, binary search can return where the value belongs to keep the data sorted.

Comparison with Linear Search

Binary search pays off when data is already sorted and searched repeatedly.

                            Comparison.java
                        
Replay: real traced execution (multi-file project)

                            public class Comparison {
    static int linearSearch(int[] arr, int target) {
        int comparisons = 0;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                System.out.println("  Linear: " + comparisons + " comparisons");
                return i;
            }
        }
        System.out.println("  Linear: " + comparisons + " comparisons (not found)");
        return -1;
    }

    static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int comparisons = 0;

        while (low <= high) {
            comparisons++;
            int mid = (low + high) / 2;

            if (arr[mid] == target) {
                System.out.println("  Binary: " + comparisons + " comparisons");
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println("  Binary: " + comparisons + " comparisons (not found)");
        return -1;
    }

    public static void main(String[] args) {
        int[] sorted = new int[32];
        for (int i = 0; i < sorted.length; i++) {
            sorted[i] = i * 2;  // even numbers 0, 2, 4, ..., 62
        }

        System.out.println("Array size: " + sorted.length);
        System.out.println("\nSearch for 30:");
        linearSearch(sorted, 30);
        binarySearch(sorted, 30);

        System.out.println("\nSearch for 63 (not found):");
        linearSearch(sorted, 63);
        binarySearch(sorted, 63);
    }
}

                        
1public static void main(String[] args)⋯36public static void main(String[] args) {37    int[] sorted = new int[32];38    for (int i = 0; i < sorted.length; i++) {⋯
2for (int i = 0; i < sorted.length; i++)pass 1 of 32⋯37int[] sorted = new int[32];38for (int i0 = 0; i < sorted.length32; i++) {39    sorted[i]0 = i0 * 2;  // even numbers 0, 2, 4, ..., 6240}⋯32 passes — pass 1 is the card abovepassisorted[i]
100
210 → 2
320 → 4
430 → 6
540 → 8
650 → 10
760 → 12
870 → 14
980 → 16
⋯ 21 more passes ⋯
31300 → 60
32310 → 62
3System.out.println("Array size: " + sorted.length);⋯42System.out.println("Array size: " + sorted.length32);43System.out.println("\nSearch for 30:");44linearSearch(sorted, 30);45binarySearch(sorted, 30);⋯outputArray size: 32

Search for 30:
4comparisons ← 0pass 1 of 21public class Comparison {2    static int linearSearch(int[] arr, int target30) {3        int comparisons→ 0 = 0;4        for (int i = 0; i < arr.length; i++) {⋯
5comparisons ← 1pass 1 of 48⋯3int comparisons = 0;4for (int i0 = 0; i < arr.length32; i++) {5    comparisons→ 1++;6    if (arr[i] == target) {⋯48 passes — pass 1 is the card abovepassiarr[i]targetcomparisons
10——0 → 1
21——1 → 2
32——2 → 3
43——3 → 4
54——4 → 5
65——5 → 6
76——6 → 7
87——7 → 8
98——8 → 9
⋯ 37 more passes ⋯
4730——30 → 31
4831——31 → 32
6if (arr[i] == target)⋯5comparisons++;6if (arr[i]30 == target30) {7    System.out.println("  Linear: " + comparisons16 + " comparisons");8    return i15;9}⋯output  Linear: 16 comparisons
7linearSearch(sorted, 30);⋯43System.out.println("\nSearch for 30:");44linearSearch(sorted, 30);45binarySearch(sorted, 30);⋯
8high ← 31, comparisons ← 0pass 1 of 2⋯15static int binarySearch(int[] arr, int target30) {16    int low = 0, high→ 31 = arr.length32 - 1;17    int comparisons→ 0 = 0;⋯
9comparisons ← 1, mid ← 15pass 1 of 7⋯19while (low0 <= high31) {20    comparisons→ 1++;21    int mid→ 15 = (low0 + high31) / 2;⋯All 7 passes — pass 1 is the card abovepasslowarr[mid]targetcomparisonsmid
1030300 → 115
20——0 → 115
316——1 → 223
424——2 → 327
528——3 → 429
630——4 → 530
731——5 → 631
10if (arr[mid] == target)⋯23if (arr[mid]30 == target30) {24    System.out.println("  Binary: " + comparisons1 + " comparisons");25    return mid15;26} else if (arr[mid] < target) {⋯output  Binary: 1 comparisons
11binarySearch(sorted, 30);⋯44linearSearch(sorted, 30);45binarySearch(sorted, 30);4647System.out.println("\nSearch for 63 (not found):");48linearSearch(sorted, 63);49binarySearch(sorted, 63);⋯output
Search for 63 (not found):
12comparisons ← 0pass 2 of 21public class Comparison {2    static int linearSearch(int[] arr, int target63) {3        int comparisons→ 0 = 0;4        for (int i = 0; i < arr.length; i++) {⋯
13System.out.println("  Linear: " + comparisons + " comparisons (not fou…⋯10    }11    System.out.println("  Linear: " + comparisons32 + " comparisons (not found)");12    return -1;13}⋯output  Linear: 32 comparisons (not found)
14linearSearch(sorted, 63);⋯47    System.out.println("\nSearch for 63 (not found):");48    linearSearch(sorted, 63);49    binarySearch(sorted, 63);50}⋯
15high ← 31, comparisons ← 0pass 2 of 2⋯15static int binarySearch(int[] arr, int target63) {16    int low = 0, high→ 31 = arr.length32 - 1;17    int comparisons→ 0 = 0;⋯
16low ← 16pass 1 of 6⋯25    return mid;26} else if (arr[mid]30 < target63) {27    low→ 16 = mid15 + 1;28} else {⋯All 6 passes — pass 1 is the card abovepassarr[mid]midlow
1301516
2462324
3542728
4582930
5603031
6623132
17System.out.println("  Binary: " + comparisons + " comparisons (not fou…⋯31    }32    System.out.println("  Binary: " + comparisons6 + " comparisons (not found)");33    return -1;34}⋯output  Binary: 6 comparisons (not found)
18binarySearch(sorted, 63);⋯48    linearSearch(sorted, 63);49    binarySearch(sorted, 63);50}⋯

32 passes — pass 1 is the card above
pass	`i`	`sorted[i]`
1	0	0
2	1	0 → 2
3	2	0 → 4
4	3	0 → 6
5	4	0 → 8
6	5	0 → 10
7	6	0 → 12
8	7	0 → 14
9	8	0 → 16
⋯ 21 more passes ⋯
31	30	0 → 60
32	31	0 → 62

48 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`	`comparisons`
1	0	—	—	0 → 1
2	1	—	—	1 → 2
3	2	—	—	2 → 3
4	3	—	—	3 → 4
5	4	—	—	4 → 5
6	5	—	—	5 → 6
7	6	—	—	6 → 7
8	7	—	—	7 → 8
9	8	—	—	8 → 9
⋯ 37 more passes ⋯
47	30	—	—	30 → 31
48	31	—	—	31 → 32

All 7 passes — pass 1 is the card above
pass	`low`	`arr[mid]`	`target`	`comparisons`	`mid`
1	0	30	30	0 → 1	15
2	0	—	—	0 → 1	15
3	16	—	—	1 → 2	23
4	24	—	—	2 → 3	27
5	28	—	—	3 → 4	29
6	30	—	—	4 → 5	30
7	31	—	—	5 → 6	31

All 6 passes — pass 1 is the card above
pass	`arr[mid]`	`mid`	`low`
1	30	15	16
2	46	23	24
3	54	27	28
4	58	29	30
5	60	30	31
6	62	31	32

Practical Use

Sorted phone books, dictionaries, indexes, and ordered tables use this same search shape.

                            Practical.java
                        
Replay: real traced execution (multi-file project)

                            public class Practical {
    record Contact(String name, String phone) implements Comparable<Contact> {
        @Override
        public int compareTo(Contact other) {
            return this.name.compareTo(other.name);
        }
    }

    static int searchByName(Contact[] contacts, String name) {
        int low = 0;
        int high = contacts.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int cmp = contacts[mid].name().compareTo(name);

            if (cmp == 0) {
                return mid;  // found
            } else if (cmp < 0) {
                low = mid + 1;  // search right
            } else {
                high = mid - 1;  // search left
            }
        }

        return -1;  // not found
    }

    public static void main(String[] args) {
        Contact[] phonebook = {
            new Contact("Alice", "555-1001"),
            new Contact("Bob", "555-1002"),
            new Contact("Charlie", "555-1003"),
            new Contact("Diana", "555-1004"),
            new Contact("Eve", "555-1005"),
            new Contact("Frank", "555-1006"),
            new Contact("Grace", "555-1007"),
            new Contact("Henry", "555-1008")
        };

        System.out.println("Phone book (" + phonebook.length + " contacts):\n");

        String[] searches = {"Charlie", "Grace", "Alice", "Zoe"};
        for (String name : searches) {
            int index = searchByName(phonebook, name);
            if (index >= 0) {
                Contact c = phonebook[index];
                System.out.println(name + ": " + c.phone());
            } else {
                System.out.println(name + ": not found");
            }
        }
    }
}

                        
1public static void main(String[] args)⋯28public static void main(String[] args) {29    Contact[] phonebook = {30        new Contact("Alice", "555-1001"),31        new Contact("Bob", "555-1002"),32        new Contact("Charlie", "555-1003"),33        new Contact("Diana", "555-1004"),34        new Contact("Eve", "555-1005"),35        new Contact("Frank", "555-1006"),36        new Contact("Grace", "555-1007"),37        new Contact("Henry", "555-1008")38    };3940    System.out.println("Phone book (" + phonebook.length8 + " contacts):\n");4142    String[] searches = {"Charlie", "Grace", "Alice", "Zoe"};43    for (String name : searches) {⋯outputPhone book (8 contacts):
2for (String name : searches)pass 1 of 4⋯42String[] searches = {"Charlie", "Grace", "Alice", "Zoe"};43for (String nameCharlie : searches) {44    int index = searchByName(phonebook, nameCharlie);45    if (index >= 0) {⋯All 4 passes — pass 1 is the card abovepassname
1Charlie
2Grace
3Alice
4Zoe
3low ← 0, high ← 7pass 1 of 4⋯9static int searchByName(Contact[] contacts, String nameCharlie) {10    int low→ 0 = 0;11    int high→ 7 = contacts.length8 - 1;12    while (low <= high) {⋯All 4 passes — pass 1 is the card abovepassnamelowhigh
1Charlie07
2Grace07
3Alice07
4Zoe07
4mid ← 3, cmp ← 1pass 1 of 13⋯11int high = contacts.length - 1;12while (low0 <= high7) {13    int mid→ 3 = (low0 + high7) / 2;14    int cmp→ 1 = contacts[mid]Contact[name=Diana, phone=555-1004].name().compareTo(nameCharlie);⋯13 passes — pass 1 is the card abovepasslowhighcontacts[mid]namemidcmp
107Contact[name=Diana, phone=555-1004]Charlie31
202Contact[name=Bob, phone=555-1002]Charlie1-1
322Contact[name=Charlie, phone=555-1003]Charlie20
407Contact[name=Diana, phone=555-1004]Grace3-3
547Contact[name=Frank, phone=555-1006]Grace5-1
667Contact[name=Grace, phone=555-1007]Grace60
707Contact[name=Diana, phone=555-1004]Alice33
802Contact[name=Bob, phone=555-1002]Alice11
900Contact[name=Alice, phone=555-1001]Alice00
⋯ 2 more passes ⋯
1267Contact[name=Grace, phone=555-1007]Zoe6-19
1377Contact[name=Henry, phone=555-1008]Zoe7-18
5high ← 2pass 1 of 3⋯19    low = mid + 1;  // search right20} else {21    high→ 2 = mid3 - 1;  // search left22}⋯All 3 passes — pass 1 is the card abovepassmidhigh
132
232
310
6low ← 2pass 1 of 7⋯17    return mid;  // found18} else if (cmp-1 < 0) {19    low→ 2 = mid1 + 1;  // search right20} else {⋯All 7 passes — pass 1 is the card abovepasscmpmidlow
1-112
2-334
3-156
4-2234
5-2056
6-1967
7-1878
7if (cmp == 0)pass 1 of 3⋯16if (cmp0 == 0) {17    return mid2;  // found18} else if (cmp < 0) {⋯All 3 passes — pass 1 is the card abovepassmid
12
26
30
8index ← 2⋯43for (String name : searches) {44    int index→ 2 = searchByName(phonebook, nameCharlie);45    if (index >= 0) {⋯
9c ← Contact[name=Charlie, phone=555-1003]pass 1 of 3⋯44int index = searchByName(phonebook, name);45if (index2 >= 0) {46    Contact c→ Contact[name=Charlie, phone=555-1003] = phonebook[index]Contact[name=Charlie, phone=555-1003];47    System.out.println(nameCharlie + ": " + c.phone());48} else {⋯outputCharlie: 555-1003All 3 passes — pass 1 is the card abovepassindexphonebook[index]namec
12Contact[name=Charlie, phone=555-1003]CharlieContact[name=Charlie, phone=555-1003]
26Contact[name=Grace, phone=555-1007]GraceContact[name=Grace, phone=555-1007]
30Contact[name=Alice, phone=555-1001]AliceContact[name=Alice, phone=555-1001]
10index ← 6⋯43for (String name : searches) {44    int index→ 6 = searchByName(phonebook, nameGrace);45    if (index >= 0) {⋯
11index ← 0⋯43for (String name : searches) {44    int index→ 0 = searchByName(phonebook, nameAlice);45    if (index >= 0) {⋯
12return -1;  // not found⋯25    return -1;  // not found26}⋯
13index ← -1⋯43for (String name : searches) {44    int index→ -1 = searchByName(phonebook, nameZoe);45    if (index >= 0) {⋯
14else⋯47    System.out.println(name + ": " + c.phone());48} else {49    System.out.println(nameZoe + ": not found");50}⋯outputZoe: not found

All 4 passes — pass 1 is the card above
pass	`name`
1	Charlie
2	Grace
3	Alice
4	Zoe

All 4 passes — pass 1 is the card above
pass	`name`	`high`
1	Charlie	7
2	Grace	7
3	Alice	7
4	Zoe	7

13 passes — pass 1 is the card above
pass	`low`	`high`	`contacts[mid]`	`name`	`mid`	`cmp`
1	0	7	Contact[name=Diana, phone=555-1004]	Charlie	3	1
2	0	2	Contact[name=Bob, phone=555-1002]	Charlie	1	-1
3	2	2	Contact[name=Charlie, phone=555-1003]	Charlie	2	0
4	0	7	Contact[name=Diana, phone=555-1004]	Grace	3	-3
5	4	7	Contact[name=Frank, phone=555-1006]	Grace	5	-1
6	6	7	Contact[name=Grace, phone=555-1007]	Grace	6	0
7	0	7	Contact[name=Diana, phone=555-1004]	Alice	3	3
8	0	2	Contact[name=Bob, phone=555-1002]	Alice	1	1
9	0	0	Contact[name=Alice, phone=555-1001]	Alice	0	0
⋯ 2 more passes ⋯
12	6	7	Contact[name=Grace, phone=555-1007]	Zoe	6	-19
13	7	7	Contact[name=Henry, phone=555-1008]	Zoe	7	-18

All 3 passes — pass 1 is the card above
pass	`mid`	`high`
1	3	2
2	3	2
3	1	0

All 7 passes — pass 1 is the card above
pass	`cmp`	`mid`	`low`
1	-1	1	2
2	-3	3	4
3	-1	5	6
4	-22	3	4
5	-20	5	6
6	-19	6	7
7	-18	7	8

All 3 passes — pass 1 is the card above
pass	`mid`
1	2
2	6
3	0

All 3 passes — pass 1 is the card above
pass	`index`	`phonebook[index]`	`name`	`c`
1	2	Contact[name=Charlie, phone=555-1003]	Charlie	Contact[name=Charlie, phone=555-1003]
2	6	Contact[name=Grace, phone=555-1007]	Grace	Contact[name=Grace, phone=555-1007]
3	0	Contact[name=Alice, phone=555-1001]	Alice	Contact[name=Alice, phone=555-1001]

Exercise: Practical.java

Implement binary search to find the first occurrence of a duplicate value in a sorted array

pass	`target`	`low`	`high`	`arr[mid]`	`mid`
1	23	0	10	23	5
2	2	0	10	—	5
3	2	0	4	—	2
4	2	0	1	2	0
5	100	0	10	—	5
6	100	6	10	—	8
7	100	9	10	—	9
8	100	10	10	—	10
9	100	11	10	—	—

pass	`target`	`low`	`high`	`arr[mid]`	`mid`
1	23	0	10	23	5
2	2	0	10	—	5
3	2	0	4	—	2
4	2	0	1	2	0
5	100	0	10	—	5
6	100	6	10	—	8
7	100	9	10	—	9
8	100	10	10	—	10
9	100	11	10	—	—

pass	`target`	`low`	`high`	`arr[mid]`	`mid`
1	23	0	10	23	5
2	2	0	10	—	5
3	2	0	4	—	2
4	2	0	1	2	0
5	100	0	10	—	5
6	100	6	10	—	8
7	100	9	10	—	9
8	100	10	10	—	10
9	100	11	10	—	—