Binary Search Searching a sorted array
233. Binary Search
You are given an array of integers nums, sorted in increasing order with no value repeated, and an array
targets. For each target, find the index in nums that holds it, or -1 if nums does not contain it.
Return an array answer with one entry per target, in the order the targets are given: answer[j] is the
index of targets[j] in nums, or -1. Indexes start at 0.
The targets come in any order, and the same target can appear more than once.
Example 1
Input: nums = [-8, -3, 0, 4, 9, 15, 21, 30]
targets = [21, 10, -8, 30]
[6,-1,0,7]Explanation: 21 is at index 6. No element equals 10, so its answer is −1. −8 is the first element, at index 0, and 30 is the last, at index 7.
Example 2
Input: nums = [5], targets = [5, 4, 6]
[0,-1,-1]Explanation: The array holds one value, at index 0. The targets 4 and 6 sit just below and just above it, and neither
is in nums.
Example 3
Input: nums = [-1000000000, -7, 0, 1000000000]
targets = [0, 0, 1000000000, -1000000000, 7]
[2,2,3,0,-1]Explanation: 0 is asked twice, and each copy gets its own answer. The smallest and largest allowed values sit at the two ends, and 7 is missing even though −7 is present.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109nums[i] < nums[i + 1](strictly increasing)1 ≤ targets.length ≤ 105-109 ≤ targets[j] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.