Binary Search Algorithm

function binarySearch(arr, target) {
    /**
     * Binary Search - Iterative Implementation
     * Time: O(log n) - logarithmic time complexity
     * Space: O(1) - constant space
     * Prerequisite: Array must be sorted
     */
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        // Calculate midpoint (avoids overflow)
        const mid = Math.floor(left + (right - left) / 2);

        if (arr[mid] === target) {
            return mid; // Found at index mid
        } else if (target < arr[mid]) {
            right = mid - 1; // Search left half
        } else {
            left = mid + 1; // Search right half
        }
    }

    return -1; // Not found
}

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    /**
     * Binary Search - Recursive Implementation
     * Time: O(log n)
     * Space: O(log n) - call stack depth
     */
    if (left > right) {
        return -1; // Base case: not found
    }

    const mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target) {
        return mid;
    } else if (target < arr[mid]) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

// Usage examples
const arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78];
console.log(binarySearch(arr, 23)); // Output: 5
console.log(binarySearch(arr, 99)); // Output: -1

// Recursive version
console.log(binarySearchRecursive(arr, 23)); // Output: 5

package main

import "fmt"

// binarySearch performs iterative binary search
// Time: O(log n), Space: O(1)
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right {
        // Calculate midpoint (avoids overflow)
        mid := left + (right-left)/2

        if arr[mid] == target {
            return mid // Found
        } else if target < arr[mid] {
            right = mid - 1 // Search left half
        } else {
            left = mid + 1 // Search right half
        }
    }

    return -1 // Not found
}

// binarySearchRecursive performs recursive binary search
// Time: O(log n), Space: O(log n) - call stack
func binarySearchRecursive(arr []int, target, left, right int) int {
    if left > right {
        return -1 // Base case
    }

    mid := left + (right-left)/2

    if arr[mid] == target {
        return mid
    } else if target < arr[mid] {
        return binarySearchRecursive(arr, target, left, mid-1)
    } else {
        return binarySearchRecursive(arr, target, mid+1, right)
    }
}

func main() {
    arr := []int{2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78}

    fmt.Println(binarySearch(arr, 23)) // Output: 5
    fmt.Println(binarySearch(arr, 99)) // Output: -1

    // Recursive version
    fmt.Println(binarySearchRecursive(arr, 23, 0, len(arr)-1)) // Output: 5
}

public class BinarySearch {
    /**
     * Binary Search - Iterative Implementation
     * Time: O(log n), Space: O(1)
     * Prerequisite: Array must be sorted
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // Calculate midpoint (avoids overflow)
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // Found
            } else if (target < arr[mid]) {
                right = mid - 1; // Search left half
            } else {
                left = mid + 1; // Search right half
            }
        }

        return -1; // Not found
    }

    /**
     * Binary Search - Recursive Implementation
     * Time: O(log n), Space: O(log n) - call stack
     */
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // Base case
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (target < arr[mid]) {
            return binarySearchRecursive(arr, target, left, mid - 1);
        } else {
            return binarySearchRecursive(arr, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};

        System.out.println(binarySearch(arr, 23)); // Output: 5
        System.out.println(binarySearch(arr, 99)); // Output: -1

        // Recursive version
        System.out.println(binarySearchRecursive(arr, 23, 0, arr.length - 1)); // Output: 5
    }
}

#include <iostream>
#include <vector>

/**
 * Binary Search - Iterative Implementation
 * Time: O(log n), Space: O(1)
 * Prerequisite: Array must be sorted
 */
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        // Calculate midpoint (avoids overflow)
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Found
        } else if (target < arr[mid]) {
            right = mid - 1; // Search left half
        } else {
            left = mid + 1; // Search right half
        }
    }

    return -1; // Not found
}

/**
 * Binary Search - Recursive Implementation
 * Time: O(log n), Space: O(log n) - call stack
 */
int binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1; // Base case
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (target < arr[mid]) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

int main() {
    std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};

    std::cout << binarySearch(arr, 23) << std::endl; // Output: 5
    std::cout << binarySearch(arr, 99) << std::endl; // Output: -1

    // Recursive version
    std::cout << binarySearchRecursive(arr, 23, 0, arr.size() - 1) << std::endl; // Output: 5

    return 0;
}