Binary Search

nums is sorted from smallest to largest and has no repeated values. Return the position of target in it, or -1 if it isn't there. Positions start at 0.

A loop over every element works, but aim for O(log n) steps by halving the search range each time.

Constraints

  • 1 ≤ length of nums ≤ 8,000
  • -1,000,000,000 ≤ nums[i], target ≤ 1,000,000,000
  • nums is strictly increasing.

Example 1

Input
nums = [-1,0,3,5,9,12]
target = 9
Output
4
Why:

9 is at position 4.

Example 2

Input
nums = [-1,0,3,5,9,12]
target = 2
Output
-1
Why:

2 is not in the array.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –