0

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.

Coder
  • 1,175
  • 1
  • 12
  • 32
  • [y for y in x if y>0][0] – dev Dec 25 '20 at 05:09
  • @ETL_Devs ah I should've specified, I want the index not the actual number! – Coder Dec 25 '20 at 06:49
  • Why not this : "[(i,j) for i,j in enumerate(nums) if j>0][0][0]" – dev Dec 25 '20 at 10:24
  • 2
    @ETL_Devs You keep suggesting linear solutions when the question very explicitly asks for logarithmic solutions. – Robby Cornelissen Dec 25 '20 at 14:22
  • yeah that would work! But since i know the array is sorted I want to improve the runtime to O(lgN) instead of O(N) – Coder Dec 25 '20 at 17:25
  • @Georgy no that is a linear solution, I'm looking for a logarithmic as my data is sorted. – Coder Dec 29 '20 at 02:09
  • @JohnD The second answer there addresses the case with sorted data. – Georgy Dec 29 '20 at 08:21
  • well before I asked this question, I searched on stackoverflow and didn't see that question. Sure, there may be some question out there which answers my question in some subpart but anyone with the same question wont be able to find that, now they will. That inherently makes this question different since I **asked** for a O(lgN) sol, i don't get why yall have to downvote and close anyone asking for questions, i searched before i posted and I'm asking a legitimate question others may have. – Coder Dec 29 '20 at 09:08
  • Yes, now they will be able to find it; that's the purpose of marking questions as duplicates: to serve as signposts to the primary question. I haven't seen anyone claim that your question was not legitimate. Simply that it was already asked and answered elsewhere on Stack Overflow. Having a question closed as a duplicate doesn't imply that you did anything wrong. – Cody Gray - on strike Dec 29 '20 at 14:47
  • @CodyGray It does imply I did something wrong when I'm not allowed to ask questions anymore (since this question was downvoted it wont allow me to post any questions from this account :/ ) – Coder Jan 07 '21 at 19:36
  • 1
    Having a question marked as a duplicate isn't relevant to the automated question blocks. Do make sure that you've read [the Help Center article](https://stackoverflow.com/help/question-bans) on the topic. Your first 4 questions have been deleted, so you won't be able to see them. They are: [1](https://stackoverflow.com/q/44877647), [2](https://stackoverflow.com/q/46084878), [3](https://stackoverflow.com/q/46186844), and [4](https://stackoverflow.com/q/46266760). It's worth checking to see if any are salvageable. – Cody Gray - on strike Jan 07 '21 at 22:56

2 Answers2

4

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.

Mark
  • 90,562
  • 7
  • 108
  • 148
  • 1
    `bisect` is definitely the right route, but I believe they're expecting `bisect_left`; this also clears up the need to test! – ti7 Dec 25 '20 at 04:33
  • great solution! I accepted this though it appears it finds the index of the first positive number instead of the first non-negative number, how could this be altered to return 2 instead of 4? I think `index = bisect_left(nums, 0)` works though so nbd! – Coder Dec 25 '20 at 06:51
  • 1
    Ah yes, @JohnD, `bisect_left` for non-negative instead of positive. – Mark Dec 25 '20 at 07:11
  • @MarkMeyer this : "[(i,j) for i,j in enumerate(nums) if j>0][0][0]" – dev Dec 25 '20 at 10:25
  • 1
    @MarkMeyer this bisect idea is very good , thanks!!! I can use it. btw , nice photographs. – dev Dec 25 '20 at 14:25
  • 1
    @ETL_Devs that's unfortunately BOTH linear time _and_ allocates a second new list! Even using a generator and `next` `next(i for i, x in enumerate(y) if x >= 0)` will be linear-time because it's doing a linear search, rather than a [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm), like [`bisect` does](https://docs.python.org/3/library/bisect.html#bisect.insort_left) – ti7 Dec 26 '20 at 14:05
  • @ti7 , i will definitely check time difference between bisect and linear iteration on a very large list – dev Dec 26 '20 at 14:37
-2
def find(nums):    
   leave = 0 
   index = -1   
   for num in nums:
       if leave = 0
          index += 1
          if num > -1:
             leave = 1
   print(index)
   return(index)

Try this. Index starts at -1 cause if the first element is positive, it still increments once. Leave is just to indicate to stop the search.

Dulnath Vanderbona
  • 7
  • 3