In case one, a simple Binary search algorithm - Wikipedia, the free encyclopedia[^] should do it, assumign there is no "bad" data. When you data goes bad, that's different, and it becomes necessary to actually search the whole array - if there is one bad value, then it's likely there are more. But the alternative to both is to to it all while you fill the array - since that is already a time consuming process (compared to a search of the results) adding a little extra checking to find the first negative as you fill the values is trivial, and allows you to cope with the second case as well.
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...