使用二进制搜索的多个键的最后一个索引？
我在排序数组中多次出现一个键，我想对它们执行二进制搜索，正常的二进制搜索为具有多次出现的键返回一些随机索引，其中我想要该键的最后一次出现的索引。
int data[] = [1,2,3,4,4,4,4,5,5,6,6]; int key = 4; int index = upperBoundBinarySearch(data, 0, data.length-1, key); Index Returned = 6 此答案中的Java实现查找第一次出现的键。 有关如何更改以查找最后一次出现的评论，但该建议会导致无限循环。 不过，这个想法似乎很合理。
编辑：经过一些研究，我在The Algo Blog上找到了一个简洁的解决方案 。 由于第一次找到的匹配不一定是必需的，因此您需要跟踪到目前为止的“最佳”匹配。 当你得到一个匹配时，你存储它并继续在该匹配右边的二进制搜索（ low = mid + 1 ）。
public static int binarySearch(int[] a, int key) { return binarySearch(a, 0, a.length, key); } private static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; int found = -1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) { low = mid + 1; } else if (midVal > key) { high = mid - 1; } else { found = mid; // For last occurrence: low = mid + 1; // For first occurrence: // high = mid - 1; } } return found; }
此更改保持O(log n)复杂性。 实际上，性能取决于应用程序。 当arrays的长度远大于所寻找的密钥的重复量时，对最后一次出现的线性搜索可能更快。 但是当存在大量重复时，这种修改后的二进制搜索可能更可取。
想必要一个O（log N）解决方案？ （否则你可以做一个线性搜索。）
在C ++中，一种可能性（多个）是使用std :: upper_bound 。 这将为您提供比您要求的更大的第一个元素的迭代器，因此您需要检查前一个元素。 这确实是O（log N） 。
我不知道Java是否提供了这种标准的库方法。 但是， upper_bound的伪代码在上面的链接中给出，并且应该很容易重新实现。
好吧，多亏@Mattias，这个算法听起来不错。 无论如何，我已经完成了自己的工作，似乎我可以提供更好的结果，但是如果有人可以帮助我衡量我和@Mattias的复杂性，或者任何一个人有更好的解决方案，那么欢迎……无论如何，这是我找到的问题的解决方案，
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; }
这是第一次出现，我也用另一个类似的post更新相同的第一次出现在二进制搜索中
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; }
当你找到钥匙。 而不是返回它在数组上执行顺序搜索以获取最后一个。 这将是O（N）解决方案。
在二进制搜索中，您将键与数组数据[i]的元素进行比较。 要获得最后一个匹配的索引，您应该更改比较函数，以便即使key等于data [i]也等于data [i + 1]，它也会给出不等式。
int upperBoundBinarySearch(int data[],int start, int end, int key) { while(start < end) { int middle = start + (end-start)/2; if (data[middle] == key && (middle == end || data[middle+1] != key)) return middle; if (data[middle] > key) end = middle; else { if (start == middle) return start; start = middle; } } return start; }