Binary Search Algorithm

The binary search algorithm is an efficient method for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

What is Binary Search Algorithm?

Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is equal to the middle element of the array, the search is complete. If the target value is less than the middle element, the search continues on the left half of the array. If the target value is greater than the middle element, the search continues on the right half of the array. This process is repeated until the target value is found or the subarray size becomes zero.

How Binary Search Works

The binary search algorithm works by comparing the target value to the middle element of the sorted array. If the target value is equal to the middle element, the search is complete. If the target value is less than the middle element, the search continues on the left half of the array. If the target value is greater than the middle element, the search continues on the right half of the array. This process is repeated until the target value is found or the subarray size becomes zero.

Conditions to apply Binary Search Algorithm in a Data Structure

The binary search algorithm can be applied to any sorted data structure, such as an array or a linked list. The data structure must be sorted in order for the binary search algorithm to work correctly. If the data structure is not sorted, the binary search algorithm will not be able to find the target value.

Binary Search Algorithm Implementation

The binary search algorithm can be implemented using both iterative and recursive approaches.

The iterative approach is generally preferred due to its lower space complexity.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
 
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 5;
const result = binarySearch(arr, target);
console.log(result); // Output: 4

Time Complexity: O(log n) Space Complexity: O(1) for iterative implementation, O(log n) for recursive implementation

Steps:

Start with the middle element of the sorted array.
If the target value is equal to the middle element, the search is complete.
If the target value is less than the middle element, repeat the search on the left half of the array.
If the target value is greater than the middle element, repeat the search on the right half of the array.
Continue this process until the target value is found or the subarray size becomes zero.

Parameters:

arr (Array): The sorted array in which to search for the target value.
target (Number): The value to search for within the array.

Returns:

(Number): The index of the target value within the array if found, otherwise -1.

The recursive approach to Binary Search Algorithm

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1;
    }
 
    let mid = Math.floor((left + right) / 2);
 
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}
 
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 5;
const result = binarySearchRecursive(arr, target);
console.log(result); // Output: 4

Time Complexity: O(log n) Space Complexity: O(log n)

Steps:

Start with the middle element of the sorted array.
If the target value is equal to the middle element, the search is complete.
If the target value is less than the middle element, repeat the search on the left half of the array.
If the target value is greater than the middle element, repeat the search on the right half of the array.
Continue this process until the target value is found or the subarray size becomes zero.

Parameters:

arr (Array): The sorted array in which to search for the target value.
target (Number): The value to search for within the array.
left (Number): The left index of the subarray to search.
right (Number): The right index of the subarray to search.

Returns:

(Number): The index of the target value within the array if found, otherwise -1.

How does Binary Search Algorithm work?

The binary search algorithm works by repeatedly dividing the search interval in half. If the target value is equal to the middle element of the array, the search is complete. If the target value is less than the middle element, the search continues on the left half of the array. If the target value is greater than the middle element, the search continues on the right half of the array. This process is repeated until the target value is found or the subarray size becomes zero.

Binary Search Visualizer

You can visualize the binary search algorithm using the following interactive tool: Binary Search Visualizer (opens in a new tab)

Applications of Binary Search Algorithm

The binary search algorithm is commonly used in various applications, such as:

Searching for an element in a sorted array.
Finding the square root of a number.
Implementing binary search trees.
Searching for an element in a sorted linked list.
Implementing the lower bound and upper bound functions in algorithms.

Linear Search Git Tutorial