Binary Search is an efficient algorithm for finding an element in a sorted array or collection. It works by repeatedly dividing the search interval in half and comparing the target value (key) with the middle element.
This article shows you how the Binary search algorithm works, and gives two examples (basic, and advanced) to demonstrate the efficiency of Binary Search.
How Binary Search Works?
- Start with two pointers:
low(beginning of the array) andhigh(end of the array). - Find the middle element using: mid=low+(high−low)/2
- Compare the key with the middle element:
- If the key matches the middle element, return its index.
- If the key is smaller, search the left half (
high = mid - 1). - If the key is larger, search the right half (
low = mid + 1).
- Repeat until
lowexceedshighor the key is found. - If the key is not found, return
-1.
1. Binary Search Program in Java (Basic example)
This program example demonstrates Binary Search on a sorted array of integers.
package com.javacodepoint.search;
public class BasicBinarySearch {
public static int binarySearch(int[] array, int key) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // Calculate mid to prevent overflow
if (array[mid] == key) {
return mid; // Key found, return index
} else if (array[mid] < key) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] numbers = { 10, 20, 30, 40, 50 };
int key = 30;
int result = binarySearch(numbers, key);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found.");
}
}
}
2. Binary Search in Java Program (Advanced example)
This program example demonstrates Binary Search on a sorted list of custom objects. The search is performed based on a specific property (e.g., id).
package com.javacodepoint.search;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
@Override
public String toString() {
return "Employee{id=" + id + ", name='" + name + "'}";
}
}
public class AdvancedBinarySearch {
public static int binarySearch(List<Employee> employees, int key) {
int low = 0;
int high = employees.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
Employee midEmployee = employees.get(mid);
if (midEmployee.getId() == key) {
return mid; // Key found
} else if (midEmployee.getId() < key) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return -1; // Key not found
}
public static void main(String[] args) {
List<Employee> employees = new ArrayList<>();
employees.add(new Employee(101, "Alice"));
employees.add(new Employee(102, "Bob"));
employees.add(new Employee(103, "Charlie"));
// Sort the list by ID (Binary Search requires a sorted collection)
Collections.sort(employees, Comparator.comparingInt(Employee::getId));
int key = 102;
int result = binarySearch(employees, key);
if (result != -1) {
System.out.println("Employee found: " + employees.get(result));
} else {
System.out.println("Employee not found.");
}
}
}
Key Differences Between the above Two Examples
| Aspect | Basic Example | Advanced Example |
|---|---|---|
| Data Type | 1D array of integers | List of custom objects (Employee) |
| Search Target | Integer | Integer (id property) |
| Result | Index of the key | Object matching the search criteria |
| Flexibility | Limited to primitive types | Works with any data structure |
Key Points to Remember
- Binary Search Requirements:
- The dataset must be sorted.
- You may need to sort a collection before performing a Binary Search.
- Time Complexity:
- O(logn), where n is the size of the dataset.
- Much faster than Linear Search for large datasets.
Read also: Linear Search, Interpolation Search, Fibonacci Search, Exponential Search, Ternary Search, and Jump Search.