First Occurrence of Number in Binary Search? I am trying to write a function, where given a sorted array, and a number, it returns the FIRST index of that number.

Is this correct? Code is in Ruby, but even if you don't know Ruby, you can pretty much understand the syntax.

def first(array, n)
        if(array.size == 0)
           return -1
        end

        l = 0
        u = array.size - 1

        #LOOP INVARIANT:
        # l &lt;= startIndex &lt;= u

        while( l != u) 
         #LOOP TERMINATES when l = u. 
         #this occurs if we reach the far right or far left without finding the #
         #or if we found the start index of the number


            m = (l+u)/2
            if(array[m] &gt; n)
                u = m -1    # l &lt;= startIndex &lt;= u

            elsif(array[m] &lt; n)
                l = m + 1   # l &lt;= startIndex &lt;= u

            elsif(array[m] == n)
                u = m       # l &lt;= startIndex &lt;= u

            end

            #LOOP always terminates because we're narrowing the range by changing l or u.
            #if there's 1 element, finding the midpoint won't narrow the range, 
            #but the while condition ends the loop anyway.
        end

        if(array[u] == n)
           return u
        else
           return -1
        end

    end
Not exactly a code review, but did you know that ruby 2 introduces binary search for arrays ? 

See : Array#bsearch. 

your problem could be solved like this: 

myarray.each_with_index.to_a.bsearch{|(x,index)| x == n}
# =&gt; if found, returns an array containing the number and the index