DacCum

Бинарный поиск

Feb 25th, 2021 (edited)
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.72 KB | None | 0 0
  1. int binarySearch(int *a, int left, int right, int key, char mode) {
  2.     if(left <= right) { //якщо границі не зімкнулись, то виконувати
  3.         if(mode == '+') {   //якщо масив відсортований в порядку зростання
  4.             int middle = (left + right) / 2; //індекс центрального елемента
  5.             if(key == a[middle])  //якщо шуканий елемент збігся з центральнім, (базовий випадок)
  6.                 return middle; //то повернути індекс цього елемента
  7.             else if(a[middle] < key) //якщо шукане більше центрального значення, (рекурсивний випадок)
  8.                 return binarySearch(a, middle + 1, right, key, mode); //то рекурсивно викликати функцію змістивши ліву межу пошуку
  9.             else //якщо ж ні, (тобто шукане менше центрального, теж рекурсивний випадок)
  10.                 return binarySearch(a, left, middle - 1, key, mode); то рекурсивно викликати функцію змістивши праву межу пошуку
  11.         }  
  12.         if(mode == '-') {   //якщо масив відсортований в порядку спадання
  13.             int middle = (left + right) / 2; //індекс центрального елемента
  14.             if(key == a[middle]) //якщо шуканий елемент збігся з центральнім, (базовий випадок)
  15.                 return middle; //то повернути індекс цього елемента
  16.             else if(a[middle] > key) //якщо шукане менше центрального значення, (рекурсивний випадок)
  17.                 return binarySearch(a, middle + 1, right, key, mode); //то рекурсивно викликати функцію змістивши ліву межу пошуку
  18.             else //якщо ж ні, (тобто шукане менше центрального, теж рекурсивний випадок)
  19.                 return binarySearch(a, left, middle - 1, key, mode); //то рекурсивно викликати функцію змістивши праву межу пошуку
  20.         }
  21.     } else //якщо границі зімкнулись, але функція не повернула значення індексу(тобто шуканого елемета немає в масиві)
  22.         return -1;  //то повернути -1 (неможливе для індексу значення)
  23. }
  24.  
Add Comment
Please, Sign In to add comment