Бинарный поиск рекурсивного количества звонков? - PullRequest
Новая
       10

Бинарный поиск рекурсивного количества звонков?

0 голосов
/ 08 мая 2018

Поэтому мне было интересно, что в моей книге рекурсивный бинарный поиск реализован следующим образом: 

 private static int bin(int[] arr, int low, int high, int target){
     counter++; //ignore this, it was to count how many calls this function invocated
     if(low > high) return -1;
     else{
         int mid = (low+high) / 2;
         if(target == arr[mid]) return mid;
         else if(target < arr[mid]) return bin(arr, low, mid-1, target);
         else return bin(arr, mid + 1, high, target);
     }

 }

И в нем говорится, что «если n, количество элементов, является степенью 2, выразите n как степень 2 ... Случай 3: ключ не находится в массиве, и его значение находится между [ 0] и a [n-1]. Здесь число сравнений, определяющих, что ключа нет в массиве, равно показателю степени. Сравнений будет на одно меньше, чем в худшем случае. "

Но когда я сел и нашел количество вызовов функций, используя массив {1,2,3,4,5,6,7,9} и клавишу 8, количество вызовов было 4. В книге сказано: количество СРАВНЕНИЙ равно 3 (что исключает 3-ю строку, которую я предполагаю?), но я почти уверен, что количество вызовов функций равно 4. Я также обобщил это для итеративной реализации бинарного поиска и обобщил, что число Итерации, или рекурсивные вызовы функций, всегда пола (лог базы 2 (n)) + 1.

Можете объяснить, что здесь происходит?

1 Ответ

0 голосов
/ 08 мая 2018

Только 3 target == arr[mid] сравнения сделаны. На четвертой итерации достигается базовый случай if(low > high), поэтому сравнение никогда не проводится. Как вы заявили: «Здесь количество сравнений для определения того, что ключа нет в массиве, равно показателю степени». Вы правы в том, что мы не имеем дело с оператором сравнения в строке 3. Нас интересует только оператор сравнения для нашего целевого значения.

Давайте посмотрим на итерации, пока не будет достигнут ни один из 2 базовых вариантов.

Двоичный поиск для 8 в массиве {1,2,3,4,5,6,7,9}

Первая итерация: 

low = 0
high = 7
mid = 3
arr[mid] = 4
(target == arr[mid]) == false

Вторая итерация: 

low = 4
high = 7
mid = 5
arr[mid] = 6
(target == arr[mid]) == false

Третья итерация: 

low = 7
high = 7
mid = 7
arr[mid] = 7
(target == arr[mid]) == false

Четвертая итерация: 

low = 8
high = 7
low > high == true

Кроме того, обозначение Big O - O (log n). + 1 считается незначительным в Big O и поэтому не учитывается. Пожалуйста, смотрите этот список в Википедии, чтобы упорядочить функции Big O от самых быстрых до самых медленных.

...