Binary Search

Given an array of integers arr sorted in ascending order and a target value, return the index at which the target appears, or -1 if it is not present. Because…

Given an array of integers `arr` sorted in ascending order and a target value, return the index at which the target appears, or `-1` if it is not present. Because the array is sorted, the search space can be halved on every comparison — aim for an O(log n) algorithm. All values in the array are distinct.

- `1 <= arr.length <= 10^4` - `-10^4 <= arr[i] <= 10^4` - `-10^4 <= target <= 10^4` - The array is sorted in strictly ascending order. - All values in the array are distinct.

Example 1: input arr = [-5, -1, 3, 7, 11], target = 11; output 4. arr[4] = 11 equals the target, so the last index is returned.

Example 2: input arr = [-5, -1, 3, 7, 11], target = 5; output -1. The closed interval shrinks until low passes high without landing on 5, so -1 is returned.

Example 3: input arr = [5], target = 5; output 0. A single-element array: the middle index is 0, and arr[0] equals the target, so 0 is returned.

Category: Sorting & Searching. Topic: binary-search. Difficulty: Easy. Patterns: binary-search.