Binary Search

Binary Search is an efficient search algorithm primarily used to find a specified element within a sorted array. The fundamental idea of Binary Search involves repeatedly halving the search range, thereby reducing the time complexity from linear O(n) to logarithmic O(log n).

In practice, the algorithm starts by comparing with the middle element of the sorted array. If this middle element equals the target value, its index is returned; if it is greater than the target, the search continues in the left half of the array; and if it is less than the target, the search proceeds to the right half. This process repeats until the target element is found or the search range becomes empty.

The time complexity of Binary Search is O(log n), where n represents the size of the sorted array. Since this algorithm relies on a pre-sorted array as its foundation, its applicability is relatively limited compared to linear search. However, it offers significant advantages in scenarios involving frequent searches, large dataset sizes, or multiple lookup operations.

It is important to note that when implementing Binary Search, one must ensure the correctness of the sorted array and carefully handle edge cases, such as empty arrays or arrays containing only a single element.

Code

::: code-tabs
@tab Java

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            // Calculate the middle index to avoid integer overflow
            int mid = left + (right - left) / 2; 
            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // Return -1 to indicate the element was not found
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        
        // Perform the search and store the result
        int result = binarySearch(arr, target);
        
        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

@tab JavaScript

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        // Calculate the middle index using Math.floor for precision
        let mid = Math.floor((left + right) / 2); 
        
        if (arr[mid] === target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Return -1 to indicate the element was not found
    return -1;
}

const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const target = 23;

// Perform the search and store the result
const result = binarySearch(arr, target);

if (result === -1) {
    console.log("Element not found in the array.");
} else {
    console.log("Element found at index " + result);
}

@tab Python

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        # Calculate the middle index using integer division //
        mid = (left + right) // 2 
        
        if arr[mid] == target:
            return mid
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    # Return -1 to indicate the element was not found
    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

# Perform the search and store the result
result = binary_search(arr, target)

if result == -1:
    print("Element not found in the array.")
else:
    print("Element found at index", result)

@tab Go

package main
import "fmt"

func binarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    
    for left <= right {
        mid := (left + right) / 2
        
        if arr[mid] == target {
            return mid
        }
        
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    // Return -1 to indicate the element was not found
    return -1
}

func main() {
    arr := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    target := 23
    
    // Perform the search and store the result
    result := binarySearch(arr, target)
    
    if result == -1 {
        fmt.Println("Element not found in the array.")
    } else {
        fmt.Println("Element found at index", result)
    }
}

@tab C

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        // Calculate the middle index to avoid potential integer overflow
        int mid = left + (right - left) / 2; 
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Return -1 to indicate the element was not found
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    
    // Calculate the size of the array dynamically
    int size = sizeof(arr) / sizeof(arr[0]);
    
    int target = 23;
    
    // Perform the search and store the result
    int result = binarySearch(arr, size, target);
    
    if (result == -1) {
        printf("Element not found in the array.\n");
    } else {
        printf("Element found at index: %d\n", result);
    }
    
    return 0;
}

@tab C++

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        // Calculate the middle index to avoid potential integer overflow
        int mid = left + (right - left) / 2; 
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Return -1 to indicate the element was not found
    return -1;
}

int main() {
    std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    
    int target = 23;
    
    // Perform the search and store the result
    int result = binarySearch(arr, target);
    
    if (result == -1) {
        std::cout << "Element not found in the array." << std::endl;
    } else {
        std::cout << "Element found at index: " << result << std::endl;
    }
    
    return 0;
}

@tab PHP

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        // Calculate the middle index using floor for precision
        $mid = floor(($left + $right) / 2); 
        
        if ($arr[$mid] == $target) {
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    // Return -1 to indicate the element was not found
    return -1;
}

$arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$target = 23;

// Perform the search and store the result
$result = binarySearch($arr, $target);

if ($result == -1) {
    echo "Element not found in the array.";
} else {
    echo "Element found at index: " . $result;
}
?>

:::