Binary search that considers magic value as not present

TombstoneBinarySearch.java

public class TombstoneBinarySearch {
	public static int binarySearch(long[] a, int fromIndex, int toIndex, long key, long tombstone) {
		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			final int origMid = mid;
			long midVal = a[mid];
			
			//Search upwards until we either run out of headroom, or find a
			//non-tombstone
			while(midVal == tombstone){
				mid++;
				if(mid > high){
					//All values in high range are tombstones - search downward
					mid = origMid;
					midVal = a[mid];
					break;
				}
				midVal = a[mid];
			}
			
			//This block is only hit if the above fails, which means we need
			//to search downwards from what is now the original midpoint
			while(midVal == tombstone){
				mid--;
				if(mid < low){
					//Not found in top half of range, as per above, and
					//apparently not found below.
					return -(low + 1);
				}
				midVal = a[mid];
			}

			if (midVal < key)
				low = mid + 1;
			else if (midVal > key)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1); // key not found.
	}
}