Binary Search

Binary search is a search algorithm that is commonly used in computer science to efficiently search for a target value in a sorted list or array. It works by dividing the search space in half at each step until the target value is found or the search space is exhausted. Binary search is a more efficient algorithm than linear search for large lists, as it has a time complexity of O(log n), where n is the size of the list.

Algorithm

Here is the basic algorithm for binary search:

Compare the target value to the middle element of the list.
If the target value matches the middle element, return its index.
If the target value is less than the middle element, search the left half of the list.
If the target value is greater than the middle element, search the right half of the list.
Repeat the process until the target value is found or the search space is exhausted.

Implementation.

Here is an example implementation of binary search in Java.

Main


              1234567891011121314151617
            
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
  
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

This implementation takes an array of integers and a target element as input and returns the index of the target element in the array. If the target element is not found, it returns -1.

Optimizations

There are several ways to optimize the binary search algorithm, such as:

Binary search can also be implemented recursively, which can make the code more concise and easier to read.
Binary search can also be implemented iteratively, which can be more efficient than the recursive implementation due to lower overhead.
The midpoint calculation can be optimized to prevent integer overflow by using (left + right) >>> 1 instead of (left + right) / 2.

Advantages	Disadvantages
Binary search is more efficient than linear search for large lists, as it has a time complexity of O(log n).	Binary search requires the list to be sorted, which can be a limitation in some cases.
Binary search can be used to find the index of a specific element in a sorted array, which can be useful for many applications.	Binary search may not be the best choice for small lists, as the overhead of the algorithm can outweigh its benefits.
Binary search can be optimized in various ways to improve its performance.

1. What is the time complexity of binary search?

2. What is the main advantage of binary search over linear search?

Everything was clear?

Thanks for your feedback!

Section 2. Chapter 5