All Problems
EasyBinary SearchArrayDivide and Conquer

Binary Search Algorithm

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

📋Problem Statement

Given a sorted array of integers and a target value, find the index of the target value in the array. If the target is not found, return -1. The array is sorted in ascending order and contains no duplicates.

💡Examples

1Example 1
Input: arr = [1, 3, 5, 7, 9, 11, 13, 15], target = 7
Output: 3
Explanation: The value 7 is at index 3 in the array.
2Example 2
Input: arr = [1, 3, 5, 7, 9, 11, 13, 15], target = 6
Output: -1
Explanation: The value 6 is not in the array.

⚠️Constraints

  • •1 <= arr.length <= 10^4
  • •-10^4 < arr[i], target < 10^4
  • •All integers in arr are unique
  • •arr is sorted in ascending order

🧠Approach

Binary search works by repeatedly dividing the search interval in half: 1. Initialize two pointers: left at the start, right at the end 2. Find the middle element 3. If middle equals target, return the index 4. If target is greater, search the right half (left = mid + 1) 5. If target is smaller, search the left half (right = mid - 1) 6. Repeat until found or left > right This halving strategy is what gives binary search its O(log n) efficiency.

✨Solution

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

// Example usage
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr, 7));  // Output: 3
console.log(binarySearch(arr, 6));  // Output: -1

🎯Key Points

  • 1Only works on sorted arrays - this is a prerequisite
  • 2Logarithmic time complexity makes it extremely efficient for large datasets
  • 3Use (left + (right - left) / 2) instead of (left + right) / 2 to avoid integer overflow
  • 4Can be implemented iteratively (shown) or recursively
  • 5Foundational algorithm used in many advanced techniques
Browse More Problems