Binary Search
Binary Search is a classic search algorithm that finds the position of a target value within a sorted array. It is a textbook example of a divide-and-conquer algorithm.
### How it works: 1. Begin with an interval covering the whole array (pointers `left` and `right`). 2. Calculate the middle index `mid`. 3. If the search key is less than the item in the middle of the interval, narrow the interval to the lower half. 4. Otherwise, narrow it to the upper half. 5. Repeatedly check until the value is found or the interval is empty.
Binary search works on **sorted** arrays. It is significantly faster than linear search with a time complexity of `O(log n)`.
### How it works: 1. Begin with an interval covering the whole array (pointers `left` and `right`). 2. Calculate the middle index `mid`. 3. If the search key is less than the item in the middle of the interval, narrow the interval to the lower half. 4. Otherwise, narrow it to the upper half. 5. Repeatedly check until the value is found or the interval is empty.
Binary search works on **sorted** arrays. It is significantly faster than linear search with a time complexity of `O(log n)`.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 < nums[i], target < 10^4
- All the integers in nums are unique.
- nums is sorted in ascending order.
TimeO(O(log n))
SpaceO(O(1))
Ready to startStep 0 / 0
TypeScript