18

7

I'm tinkering with some code and I realized something I never knew. A normal binary search will return a random index in a data set for a key that occurs more than once. How can I modify this code below to return the *first occurrence*? Is this something people do?

```
//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
return bSearchVal(a, 0, a.length, key);
}
private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
int toIndex, long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid].val;
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return (low); // key not found. return insertion point
}
```

1

Cool - I get to rep-whore my own question and answer... http://stackoverflow.com/questions/4948162/how-can-i-better-understand-the-one-comparison-per-iteration-binary-search explains a form of the binary search that can find the first item > or >=, or the last item < or <=.

– Steve314 – 2011-07-13T08:57:02.797Hah, thanks! I'll take a look. Every once in a while I notice something like this and I think 'you know nothing'. – Amir Afghani – 2011-07-13T08:59:35.563