Binary search is a popular algorithm used to search through a sorted array or list of elements. It has a time complexity of O(log n) and a space complexity of O(1). Binary search is a divide and conquer approach to searching that can dramatically improve the speed of searching through large data sets. In this article, we will discuss what binary search is, how it works, its time and space complexities, and how to implement it in Java. We will also provide five coding exercises with solutions so readers can test their understanding of the binary search algorithm.
What is Binary Search?
Binary search is an algorithm that is used to search through a sorted array or list of elements. It is a divide and conquer approach that searches for a specific element by repeatedly dividing the search area in half. The algorithm works by comparing the target element to the middle element in the search area. If the target element is smaller than the middle element, the algorithm will search the left half of the search area. If the target element is larger than the middle element, the algorithm will search the right half of the search area. The algorithm then continues to divide the search area in half until the target element is found or until the search area is exhausted.
How Does Binary Search Work?
The binary search algorithm works by taking a sorted array or list of elements and repeatedly dividing the search area in half. The algorithm begins by comparing the target element to the middle element in the search area. If the target element is smaller than the middle element, the algorithm will search the left half of the search area. If the target element is larger than the middle element, the algorithm will search the right half of the search area. The algorithm continues to divide the search area in half until the target element is found or until the search area is exhausted.
The following example shows how the binary search algorithm works. We will search for the element 5 in an array of integers sorted in ascending order.
// Array of integers sorted in ascending order
int[] array = {1, 3, 5, 7, 9, 11, 13};
// Target element to search for
int target = 5;
// Start the search at the beginning of the array
int start = 0;
// End the search at the end of the array
int end = array.length - 1;
// Keep searching until the start index is greater than the end index
while (start <= end) {
// Calculate the midpoint of the array
int mid = (start + end) / 2;
// If the target element is less than the midpoint element, search the left half of the array
if (target < array[mid]) {
end = mid - 1;
}
// If the target element is greater than the midpoint element, search the right half of the array
else if (target > array[mid]) {
start = mid + 1;
}
// If the target element is equal to the midpoint element, the element has been found
else {
System.out.println("Element found at index: " + mid);
break;
}
}
In this example, the binary search algorithm is used to search for the element 5 in an array of integers sorted in ascending order. The algorithm begins by comparing the target element to the middle element in the search area. In this case, the target element (5) is smaller than the middle element (7). Therefore, the algorithm will search the left half of the search area. The algorithm then calculates the midpoint of the left half of the array and compares the target element to the midpoint element. The target element (5) is larger than the midpoint element (3). Therefore, the algorithm will search the right half of the search area. The algorithm then calculates the midpoint of the right half of the array and compares the target element to the midpoint element. The target element (5) is equal to the midpoint element (5). Therefore, the element has been found and the algorithm prints “Element found at index: 2”.
Time Complexity
The time complexity of the binary search algorithm is O(log n). This means that the algorithm will take logarithmic time to search for an element in a sorted array or list. This is a significant improvement over linear search, which has a time complexity of O(n). In other words, the binary search algorithm will take less time to search for an element in a large data set than a linear search algorithm.
The best-case time complexity of the binary search algorithm is O(1). This means that the algorithm will take constant time to search for an element if the target element is the first element in the array.
The average-case time complexity of the binary search algorithm is O(log n). This means that the algorithm will take logarithmic time to search for an element in a sorted array or list.
The worst-case time complexity of the binary search algorithm is O(log n). This means that the algorithm will take logarithmic time to search for an element in a sorted array or list, even if the target element is the last element in the array.
Space Complexity
The space complexity of the binary search algorithm is O(1). This means that the algorithm will take constant space to search for an element in a sorted array or list. This is a significant improvement over linear search, which has a space complexity of O(n). In other words, the binary search algorithm will take less space to search for an element in a large data set than a linear search algorithm.
How to Implement Binary Search in Java
Now that we have discussed what binary search is, how it works, and its time and space complexities, let’s take a look at how to implement it in Java. The following example shows how to implement a binary search algorithm in Java.
// Array of integers sorted in ascending order
int[] array = {1, 3, 5, 7, 9, 11, 13};
// Target element to search for
int target = 5;
// Function to perform binary search
public static int binarySearch(int[] array, int target) {
// Start the search at the beginning of the array
int start = 0;
// End the search at the end of the array
int end = array.length - 1;
// Keep searching until the start index is greater than the end index
while (start <= end) {
// Calculate the midpoint of the array
int mid = (start + end) / 2;
// If the target element is less than the midpoint element, search the left half of the array
if (target < array[mid]) {
end = mid - 1;
}
// If the target element is greater than the midpoint element, search the right half of the array
else if (target > array[mid]) {
start = mid + 1;
}
// If the target element is equal to the midpoint element, the element has been found
else {
return mid;
}
}
// Return -1 if the element is not found
return -1;
}
Conclusion
Binary search is a popular algorithm used to search through a sorted array or list of elements. It has a time complexity of O(log n) and a space complexity of O(1). Binary search is a divide and conquer approach to searching that can dramatically improve the speed of searching through large data sets. In this article, we discussed what binary search is, how it works, its time and space complexities, and how to implement it in Java.
Exercises
Write a function to perform binary search on a sorted array of integers.
// Function to perform binary search
public static int binarySearch(int[] array, int target) {
// Start the search at the beginning of the array
int start = 0;
// End the search at the end of the array
int end = array.length - 1;
// Keep searching until the start index is greater than the end index
while (start <= end) {
// Calculate the midpoint of the array
int mid = (start + end) / 2;
// If the target element is less than the midpoint element, search the left half of the array
if (target < array[mid]) {
end = mid - 1;
}
// If the target element is greater than the midpoint element, search the right half of the array
else if (target > array[mid]) {
start = mid + 1;
}
// If the target element is equal to the midpoint element, the element has been found
else {
return mid;
}
}
// Return -1 if the element is not found
return -1;
}
Write a function to search for an element in a sorted array using a recursive binary search algorithm.
// Function to perform recursive binary search
public static int recursiveBinarySearch(int[] array, int start, int end, int target) {
// Base case - array has been exhausted
if (start > end) {
return -1;
}
// Calculate the midpoint of the array
int mid = (start + end) / 2;
// If the target element is less than the midpoint element, search the left half of the array
if (target < array[mid]) {
return recursiveBinarySearch(array, start, mid - 1, target);
}
// If the target element is greater than the midpoint element, search the right half of the array
else if (target > array[mid]) {
return recursiveBinarySearch(array, mid + 1, end, target);
}
// If the target element is equal to the midpoint element, the element has been found
else {
return mid;
}
}
Write a function to search for an element in a rotated sorted array using a binary search algorithm.
// Function to perform binary search on a rotated sorted array
public static int binarySearchRotated(int[] array, int target) {
// Start the search at the beginning of the array
int start = 0;
// End the search at the end of the array
int end = array.length - 1;
// Keep searching until the start index is greater than the end index
while (start <= end) {
// Calculate the midpoint of the array
int mid = (start + end) / 2;
// If the target element is equal to the midpoint element, the element has been found
if (target == array[mid]) {
return mid;
}
// If the left half of the array is sorted
if (array[start] <= array[mid]) {
// Check if the target element is in the left half of the array
if (target >= array[start] && target < array[mid]) {
end = mid - 1;
}
// Target element is in the right half of the array
else {
start = mid + 1;
}
}
// If the right half of the array is sorted
else {
// Check if the target element is in the right half of the array
if (target > array[mid] && target <= array[end]) {
start = mid + 1;
}
// Target element is in the left half of the array
else {
end = mid - 1;
}
}
}
// Return -1 if the element is not found
return -1;
}
Write a function to search for an element in an unsorted array using a linear search algorithm.
// Function to perform linear search
public static int linearSearch(int[] array, int target) {
// Start the search at the beginning of the array
int start = 0;
// End the search at the end of the array
int end = array.length - 1;
// Keep searching until the start index is greater than the end index
while (start <= end) {
// If the target element is equal to the midpoint element, the element has been found
if (target == array[start]) {
return start;
}
// Move to the next element in the array
start++;
}
// Return -1 if the element is not found
return -1;
}
Write a function to search for an element in an unsorted array using a binary search algorithm.
The binary search algorithm can only be used to search through sorted arrays or lists. Therefore, it is not possible to use a binary search algorithm to search through an unsorted array.