Given an array of integers nums sorted in ascending order, search target in O(log n) runtime.
Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return -1. You must write an algorithm with `O(log n)` runtime complexity.
Invariant: At the beginning of each iteration, if target exists in nums, it must be contained in the closed interval [low, high].
Binary search applies to any monotonic search space where answers transition from false to true.
Bottleneck: Reduces 10^9 operations to ~30 operations.
Given an array of integers nums sorted in ascending order, search target in O(log n) runtime.
Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return -1. You must write an algorithm with `O(log n)` runtime complexity.
Invariant: At the beginning of each iteration, if target exists in nums, it must be contained in the closed interval [low, high].
Binary search applies to any monotonic search space where answers transition from false to true.
Bottleneck: Reduces 10^9 operations to ~30 operations.
Initialized Binary Search across interval [0 ... 5]. Searching for target = 9.