Skip to content

Instantly share code, notes, and snippets.

@bnyeggen
Created October 20, 2015 02:00
Show Gist options
  • Save bnyeggen/c812cd227c661f033f78 to your computer and use it in GitHub Desktop.
Save bnyeggen/c812cd227c661f033f78 to your computer and use it in GitHub Desktop.
Binary search that considers magic value as not present
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.
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment