Двоичный поиск в C

Я реализовал функцию поиска элементов списка, которая была бинарным поиском, возвращает индекс найденного элемента. Мое любопытство заключается в том, чтобы иметь метод бинарного поиска, который вы могли бы распечатать все вхождения элемента в списке.Двоичный поиск в C

Ниже приведен код

int Binary_Search(int *array, int chave , int N) 
{ 
int inf = 0; 
int sup = N-1; 
int meio; 
while (inf <= sup) 
{ 
     meio = inf + (sup-inf)/2; 
     if (chave == array[meio]) 
      return meio; 
     else if (chave < array[meio]) 
      sup = meio-1; 
     else 
      inf = meio+1; 
} 
return -1; 
}

часть другого источника

Как я мог бы сделать этот фрагмент кода только печатаете вхождения дублируются?

else 
{ 
    Imprime_Struct(Tabinvertida_Fornecedor[aux]->info); 
    aux=aux+1; 
    while (aux != i) 
    { 
     if (strcmp(chave, TabName[aux]->info.name)==0) 
      Print_Struct(TabName[aux]->info); 
     aux++; 
    } 
}

источник

2013-11-10 user2976298

Непонятно, что вы спрашиваете – SomeWittyUsername

Добро пожаловать в переполнение стека. Вскоре прочитайте страницу [О программе]. Ваш начальный двоичный поиск подходит для поиска массива целых чисел. Кажется, что ваш второй фрагмент имеет дело с массивом структуры данных. Is 'Imprime_Struct()' отличается от 'Print_Struct()'? Вы можете написать два варианта бинарного поиска: тот, который находит наименьший индекс, где значение равно искомому значению, и тот, который находит наибольший индекс, где значение равно искомому значению (в массиве с дубликатами). Это оба алгоритма O (log N), лучше, чем алгоритм O (N). –

Алгоритм двоичного поиска предназначен для поиска индекса элемента, который вы хотите искать в отсортированном массиве. В случае, если у вас есть несколько вхождений одного и того же элемента (которые вы ищете) в массиве, тогда он должен дать вам только первую встречную позицию индекса. Алгоритм двоичного поиска никогда не может возвращать более одного индекса, где элемент найден. –

После того, как вы получите index элемента, вы можете просто scan forward and backwards проверки для этого элемента. Поскольку массив sorted, все duplicates will be together. В worst case, когда все элементы одинаковы, этот метод будет принимать O(n)

источник

2013-11-10 15:20:53

Вы можете реализовать двоичный поиск двумя способами:

1) so that it finds the first element not smaller than given 
2) so that it finds the last element not greater than given

Использование этих двух реализаций в сочетании вы можете легко определить количество копий каждого элемента ,

Если массив содержит только integeres, не событие, должны использовать оба - просто выбрать один и поиск

1) n and n+1 
2) n-1 and n

соответственно.

Это дает вам логарифмическую сложность.

источник

2013-11-10 15:25:07

Двоичный поиск в C

ответ

Смежные вопросы