Variants of binary search.

It is possible to derive algorithms from the problem by considering the invariants. Lets apply

this technique to derive some variants of binary search.

Question: Find out the first occurrence of a key from a sorted array?

This is a variation of binary search and is not very trivial. To synthesize this algorithm let's see what invariant we may be looking for:

Clearly, if l=lower and u=upper, we are looking for a situation where x[l]=key and l+1=u in the post condition.

Obviously the precondition can be using only the first two constraints.

So we have a proof of correctness from the two conditions.

Now we can write the algorithm (courtesy Benteley)

def binsearch_1st_log(list,k):
    l=-1
    u=len(list)
    while l+1 != u:
        m=(l+u)/2
        if list[m]            l=m
        else:
            u=m
    p=u
    if p >= len(list) or list[p] != k:
          p=-1
    return p

  

This is a neat python implementation. This is also an efficient implementation of binary search.

Question 2: Search a sorted array for the first element larger than k.

The loop invariant for the above problem can be considered as the following:

x[l]<=key and x[u]>key.

The post condition should have an additional constraint l+1 = u.

This gives a very similar code as the first one:

 
def binsearch_var2(list,k):
    l=-1
    u=len(list)
    while l+1 != u:
        m=(l+u)/2
        if list[m]<=k:
            l=m
        else:
            u=m
    if u>0 and list[u-1] != k:
       return -1
    return u