Binary Search in Java

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

// 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;
}

// 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;
    }
}

// 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;
}

// 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;
}