Write a function `binarySearch(arr, target)` that returns the index of the target in a sorted array, or -1 if not found.
Problem Statement
<p>Write a function <code>binarySearch(arr, target)</code> that returns the index of the target in a sorted array, or -1 if not found.</p>
Examples
Input: arr = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: Target 9 is at index 4.
Input: arr = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: Target 2 does not exist in array.
Complexity
Time Complexity: O(log
Space Complexity: O(1)
Hints
š” Hint 1:
Binary search works on sorted arrays by dividing the search space in half.
š” Hint 2:
Use two pointers (left and right). Compare the middle element with the target.
š” Hint 3:
If mid value < target, move left = mid + 1. If mid value > target, move right = mid - 1.
Editorial & Approach
Problem Overview & Intuition
To solve Binary Search, we consider the execution characteristics of JavaScript engines. Write a function `binarySearch(arr, target)` that returns the index of the target in a sorted array, or -1 if not found. By utilizing idiomatic language constructs and clean algorithmic principles, we can accomplish this with optimal time and memory usage.
Step-by-Step Approach
- Understand Problem Contract: Identify input arguments, return type expectations, and edge cases (empty inputs, nullish values).
- Choose Core Mechanism: Use modern JavaScript patterns (binary search works on sorted arrays by dividing the search space in half).
- Implement Logic: Handle state and transformations efficiently (use two pointers (left and right). compare the middle element with the target).
- Return Result: Ensure proper return format and preserve caller context if applicable.
Optimal Implementation (JavaScript)
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;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Complexity Analysis
Time Complexity
O(log N) logarithmic binary search
Space Complexity
O(1) constant auxiliary space
Edge Cases & Corner Traps Handled
- Empty or boundary inputs (empty arrays, strings, zero length).
- Type checks and unexpected values (e.g.
null,undefined, negative numbers). - Closure preservation and memory isolation between separate invocations.