Binary Search Algorithm

Binary Search

Binary search is an algorithm used to find the position of a specific value within a sorted array efficiently.

It starts by examining the middle element of the array. If the target value matches the middle element, the search is successful, and if the target value is less than the middle element, the search continues in the lower half of the array; otherwise, it continues in the upper half.

Remember: This process has a logarithmic time complexity of 'O(log n)', where 'n' is the number of elements in the array.

Binary search is significantly faster than linear search for large arrays due to its efficient elimination of half the elements with each comparison. However, it requires the array to be sorted. If the array is not sorted, binary search cannot be applied.

Implement the binary search algorithm:

Here's a simple implementation of the binary search algorithm in JavaScript.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        // Check if target is present at mid
        if (arr[mid] === target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    // If target is not found in array
    return -1;
}

// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const target = 9;
const index = binarySearch(arr, target);
console.log("Element found at index:", index); 
// Output: Element found at index: 4

Element found at index: 4

Explanation:

This implementation assumes that the array 'arr' is sorted in ascending order. If the target is found, it returns the index of the target element in the array. If the target is not found, it returns -1.