首次出现在二分搜索中
我正在修补一些代码，我意识到我从来不知道的事情。 正常的二进制搜索将在数据集中返回多次出现的密钥的随机索引。 如何修改下面的代码以返回第一次出现 ？ 这是人们做的事吗？
//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 >> 1; long midVal = a[mid].val; if (midVal key) high = mid - 1; else return mid; // key found } return (low); // key not found. return insertion point } 找到匹配值后，您基本上需要向上走集合，直到找到不匹配的条目。
你可以通过获取一个直接低于你所寻找的密钥的索引使其更快，然后在两者之间进行二进制切换 – 但我可能会选择更简单的版本，这可能是“高效的”足够“除非你有相当多的平等条目。
Jon Skeets的新增内容：
潜在的更快实现实际上并不难实现，只添加了2行代码，以下是我的工作方式：
if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else if (low != mid) //Equal but range is not fully scanned high = mid; //Set upper bound to current number and rescan else //Equal and full range is scanned return mid;
您可以通过更清晰的匹配定义来调整现有的搜索算法。 你可以看出序列1,3,5,5,5,9中突出显示的5是第一个，因为它之前的数字（3）小于5.所以如果mid中的数组元素等于键如果[mid-1]小于key，则只将它视为匹配，其他相等的数组元素被视为大于元素。 现在你的算法变成了（在包括Jon Skeet建议返回插入点的底片之后）：
public static int binarySearch(int[] a, int key) { int low=0,high=a.length-1; while (low<=high) { int mid=(low+high) >>> 1; int midVal=a[mid]; if (midVal < key) low=mid+1; else if (mid>0 && a[mid-1]>=key) //we already know midval>=key here high=mid-1; else if (midVal==key) //found the 1st key return mid; else return ~mid; //found insertion point } return ~(a.length); //insertion point after everything }
它使用了更多的比较，但在我的基准测试中比Stev314的版本更快，可能是因为缓存效果。
您可以实现“下限”算法而不是二进制搜索。 该算法例如在C ++ / STL中使用，并且其对Java的转录是直截了当的。 下界的算法复杂度也是O（log n）作为二分搜索。 这比首先使用二进制搜索更好，而不是线性搜索第一个匹配元素 – 这将具有最坏情况行为O（n）。
如果您的数据都是完整的，那么这个黑客可以提供帮助。 它使用float数组来存储值。
float array[]; //contains all integral values int searchValue; int firstIndex = -(binarySearch(array, (float)searchValue - 0.5F) + 1);
基本上它的作用是在搜索值和它之前的整数之间找到一个值的插入索引。 由于所有值都是整数，因此它会找到第一次出现的搜索值。
此运行也是log（n）时间。
例：
import java.util.Arrays; public class BinarySearch { // considering array elements are integers float ar[] = new float[] { 1, 2, 3, 3, 4, 4, 5, 9, 9, 12, 12 }; public void returnFirstOccurrence(int key) { int firstIndex = -(Arrays.binarySearch(ar, key - 0.5F) + 1); if (ar[firstIndex] != key) System.out.println("Key doesn't exist"); else System.out.println("First index of key is " + firstIndex); } public static void main(String Args[]) throws Exception { new BinarySearch().returnFirstOccurrence(9); } }
输出：7
ps：我在几个编码竞赛中使用过这个技巧，每次都很好用。
以下算法二进制搜索第一个项目，其中一个键大于或等于您的搜索键…
while (upperbound > lowerbound) { testpos = lowerbound + ((upperbound-lowerbound) / 2); if (item[testpos] >= goal) { // new best-so-far upperbound = testpos; } else { lowerbound = testpos + 1; } }
这不是为Java编写的，我不太清楚，因此可能需要进行一些小的调整。 请注意，边界是半开放的（下限是包含的，上限是独占的），这对正确性很重要。
这可以适用于其他类似搜索 – 例如找到最后一个键<=搜索值。
这在我之前的问答中略有修改。
这是解决方案，我找到了使用二进制搜索获得在排序数组中多次出现的键的较低索引。
int lowerBound(int[] array,int fromIndex, int toIndex, int key) { int low = fromIndex-1, high = toIndex; while (low+1 != high) { int mid = (low+high)>>>1; if (array[mid]< key) low=mid; else high=mid; } int p = high; if ( p >= toIndex || array[p] != key ) p=-1;//no key found return p; }
我们必须在这段代码中稍微改变一下，使用二进制搜索来处理上限，所以这里是代码的工作副本。
int upperBound(int[] array,int fromIndex, int toIndex, int key) { int low = fromIndex-1, high = toIndex; while (low+1 != high) { int mid = (low+high)>>>1; if (array[mid]> key) high=mid; else low=mid; } int p = low; if ( p >= toIndex || array[p] != key ) p=-1;//no key found return p; }
这是scala中解决方案的变体。 使用模式匹配和递归而不是while循环来获取第一次出现。
def binarySearch(arr:Array[Int],key:Int):Int = { def binSearchHelper(lo:Int,hi:Int,mid:Int):Int = { if(lo > hi) -1 else { if(arr(mid) == key) mid else if(arr(mid) > key){ binSearchHelper(lo,mid-1,lo + (((mid-1) - lo)/2)) }else{ binSearchHelper(mid+1,hi,(mid+1) + ((hi - (mid+1))/2)) } } } binSearchHelper(0,arr.size-1,(arr.size-1)/2) } def findFirstOccurrence(arr:Array[Int],key:Int):Int = { val startIdx = binarySearch(arr,key) startIdx match { case 0 => 0 case -1 => -1 case _ if startIdx > 0 => { if(arr(startIdx - 1) < key) startIdx else { findFirstOccurrence(arr.slice(0,startIdx),key) } } } }
这应该可以解决问题
private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex, int toIndex, long key) { int low = fromIndex; int high = toIndex - 1; int result = low; 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 { result = mid; high = mid -1; } } return result;
}
对于元素的最后一次出现：
static int elementExists(int input[], int element){ int lo=0; int high = input.length-1; while(loinput[mid] ){ lo = mid+1; } else if(element < input[mid]){ high= mid-1; } else if (high != input.length-1) //Change for the Occurrence check lo = mid; else { return mid; } } return -1; }
第一次出现：
else if (lo != mid){ high = mid; }
一种方法是在整个二进制搜索中保持不变量。 在您的特定情况下，不变量将是：
-
array[low] < key -
key <= array[high]
然后，您可以使用二进制搜索最小化低和高之间的差距。 当low + 1 == high ， high就是答案。 C ++中的示例代码：
// check invariant on initial values. if (array[low] >= key) return low; if (array[high] < key) return high+1; // low + 1 < high ensures high is at least low + 2, thus // mid will always be different from low or high. It will // stop when low + 1 == high. while (low + 1 < high) { int mid = low + (high - low) / 2; if (array[mid] < key) { low = mid; // invariant: array[low] < key } else { high = mid; // invariant: array[high] >= key } } return high;
这个和你的示例代码之间的主要区别是将low和high更新到只有mid而不是mid+1或mid-1 ，因为我们检查了array[mid]的值，我们可以保证在更新边界时仍然保持不变量。 在开始搜索之前，您需要检查初始值的不变量。
我认为一种更简单的方法是将最新的mid索引存储在xs[mid] == key的结果变量中，然后继续运行二进制搜索。
这是快速的代码：
func first(xs: [T], key: T) -> Int { var lo = xs.startIndex var hi = xs.endIndex - 1 var res = -1 while lo <= hi { let mid = lo + (hi - lo) >> 1 if xs[mid] == key { hi = mid - 1; res = mid } else if xs[mid] < key { lo = mid + 1} else if xs[mid] > key { hi = mid - 1 } } return res }
此外，如果要查找键的最后一个索引，则需要进行非常小的更改（只需一行）。
func last(xs: [T], key: T) -> Int { var lo = xs.startIndex var hi = xs.endIndex - 1 var res = -1 while lo <= hi { let mid = lo + (hi - lo) >> 1 if xs[mid] == key { lo = mid + 1; res = mid } else if xs[mid] < key { lo = mid + 1} else if xs[mid] > key { hi = mid - 1 } } return res }