optimized indexed array search for greater-than number

Question

I have an array of sorted numbers:

pts = [ 0, 4, 25, 51, 72, 100 ]

Given value T, I need to find the index of the first number in the array greater than T.

if T = 2, then the correct index is 1 for value 4

dumb solution

I can do this with a linear search, but would like to optimize.

not working solution

Binary search algorithm examples find the index of an exact number..

Is there a suggested technique to solve this sort of search problem? Thanks!

Answer 1

Binary search algorithm to find t such that list[t] <= T and list[t+1] > T (or t+1 is longer than the length of the list)

Answer 2

Binary search algorithms do usually find an exact match, but the algorithm is simple, and it should be easy for you to modify it to find the first number greater than a given number. Is there a particular language you are looking for a solution in?

Answer 3

Binary search will work for that.

Typically an implementation will return a negative number to tell you about the insertion point. For example in Java, just -1-n and you have your position.