Я занимаюсь каким-то кодом, и я понял то, чего никогда не знал. Обычный двоичный поиск возвращает случайный индекс в наборе данных для ключа, который встречается более одного раза. Как я могу изменить этот код ниже, чтобы вернуть первое вхождение? Это что-то люди делают?
//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
}
Найдя подходящее значение, вам в основном нужно подобрать коллекцию, пока не найдете запись, которая не соответствует.
Вы могли бы сделать это быстрее, выбирая индекс ключа, который был бы ниже, чем тот, который вы искали, затем выполните двоичную отбивку между ними - но я, вероятно, поеду на более простую версию, которая, скорее всего, "достаточно эффективны", если у вас нет действительно большого количества одинаковых записей.
Добавление к сообщению 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;
Вы можете адаптировать существующий алгоритм поиска, просто используя более четкое определение соответствия. Вы можете сказать, что выделенный 5 в последовательности 1,3, 5, 5,5,9 является первым, потому что число перед ним (3) меньше 5. Так что если элемент массива, равный ключу, вы рассматриваете его только как совпадение, если [mid-1] меньше ключа, другие равные элементы массива обрабатываются как больше, чем элементы. Теперь вы получаете алгоритм (после включения предложения 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, в моих тестах, вероятно, из-за эффектов кеша.
Вместо бинарного поиска вы можете реализовать алгоритм "нижняя граница". Этот алгоритм используется, например, в С++/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
p.s: Я использовал этот трюк в нескольких конкурсах кодирования, и он прекрасно работал каждый раз.
Следующий алгоритм binary-search для первого элемента с ключом больше или равным вашему поисковому ключу...
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;
}
В этой теме вы можете найти полный пример бинарного поиска (рекурсивная версия) и две другие версии (основанные на исходной), которые позволяют получить первый и последний индексы данного ключа.
Для вашего удобства я добавил соответствующие тесты Junit.
Здесь вариация решения в 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(lo<high){
int mid = (lo + high )/2;
if(element >input[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] < keykey <= 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<T: Comparable>(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<T: Comparable>(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
}
Попробуйте это рекурсивное решение JavaScript. Это оптимально в том смысле, что это O (log (N))
function solve(A, e) {
function solve (A, start, end, e, bestUntilNow) {
if (start > end) {
if (A[start] === e)
return start
return bestUntilNow
} else {
const mid = start + Math.floor((end - start) / 2)
if (A[mid] === e) {
return solve(A, start, mid - 1, e, mid)
} else if (e < A[mid]) {
return solve(A, start, mid - 1, e, bestUntilNow)
} else {
return solve(A, mid + 1, end, e, bestUntilNow)
}
}
}
return solve(A, 0, A.length, e, -1)
}