Binary Search: First Occurrence of an Element

Problem: Find the first occurrence of an element in a sorted array.

Discussion: Binary search dictates that in order to find an element in a sorted array, we test the middle^[1] element (call it pivot) for equality. If key is smaller than pivot, we search in subarray before pivot. If key is bigger, we search in subarray after the pivot. If equal, then we found the element. Divide an conquer.

This is a slight variant of it. We need to keep searching left until we ensure that it's the first occurrence.

Strategy: The first idea that comes to my mind, is to use regular binary search to find the element. It may not necessarily be the first occurrence. Now, we creep up the sorted array till we find an element less than the search key or we hit the boundary of the array. The complexity of this mechanism is O(log(n)) + O(k), where n is the array length, and k is repetition of key.

The other idea is to modify binary search slightly, and keep looking for the key in subarray preceding the 'pivot', if the pivot is equal to the `key` with element previous to the pivot is same as key and array boundary is not yet hit. This is O(logn). Here is the algorithm.

binary-first (A, key, low, high)
  if low > high
    return -1
    
  mid = low + (high - low)/2
  if key = A[mid]
    if mid > 1 and A[mid-1] == key
      return binary-first(A, key, low, mid-1)
    else
      return mid
  else if key < A[mid]
    return binary-first(A, key, low, mid-1)
  else
    return binary-first(A, key, mid+1, high)  

Footnotes:
[1] middle does not have to be mid. You may wish to use a random(low, high) as your pivot. However, mid as pivot makes it easy to think in terms of.

[2] View/download Java code at GitHub and sample execution here.