Common Algorithms
Binary Search
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
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));
}
}
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.
Trace.java
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 = ;
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 = ;
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 = ;
System.out.println("Searching for " + target + ":");
binarySearchTrace(sorted, target);
}
}
Recursive Version
Binary search can also be expressed recursively by searching either the left half or the right half.
Recursive.java
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));
}
}
Finding Insertion Points
InsertionPoint.java
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));
}
}
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
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);
}
}
Practical Use
Sorted phone books, dictionaries, indexes, and ordered tables use this same search shape.
Practical.java
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");
}
}
}
}
Exercise: Practical.java
Implement binary search to find the first occurrence of a duplicate value in a sorted array