Binary Search Explained

Problem Statement

Given a sorted array of integers and a target value, find the index of the target using Binary Search. Binary Search efficiently locates an element by repeatedly dividing the search interval in half.

Example

Input: array = [2, 3, 4, 10, 40], target = 10

Output: 3 (index of 10 in the array)

Code

public class Solution {
    public int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] array = {2, 3, 4, 10, 40};
        System.out.println(sol.binarySearch(array, 10)); // 3
    }
}
            

def binary_search(array, target):
    left, right = 0, len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found

# Example usage
print(binary_search([2, 3, 4, 10, 40], 10))  # 3
            

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}

// Example usage
console.log(binarySearch([2, 3, 4, 10, 40], 10)); // 3
            

Explanation

• Start with the full array, setting pointers to the start (left) and end (right).
• Calculate the middle index and compare the middle element with the target.
• If the middle element is the target, return its index.
• If the target is greater, search the right half; if smaller, search the left half.
• Repeat until the target is found or the search space is exhausted.

Note