Python function to find the first non-negative number in a sorted list?

Question

I have a sorted list like nums = [-4,-1,0,3,10] and I want to find the index of the first non-negative integer.

A linear time solution was provided to me:

def find(nums):
  n = len(nums)
  i = 0
  while i < n and nums[i] < 0:
    i += 1
  return i

Is there a logarithmic solution to this question?

It is guaranteed that there will be a non-negative integer in the list.

Answer 1

The Python standard library has a very cool library called bisect, that will preform fast binary searches on lists. In your example, you can get the index of the first non-negative number by using bisect.bisect_right to find the "right" insertion point for zero:

from bisect import bisect_right

nums = [-4,-1,0,0,1,3,10]

index = bisect_right(nums, 0)
# 4 -- the index

nums[index]
# 1 -- the number at that index

If there are no non-negative numbers it will return an index equal to the length of the list, so you will need to test for that if it's a possibility.