Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int binarySearch(int *a, int left, int right, int key, char mode) {
- if(left <= right) { //якщо границі не зімкнулись, то виконувати
- if(mode == '+') { //якщо масив відсортований в порядку зростання
- int middle = (left + right) / 2; //індекс центрального елемента
- if(key == a[middle]) //якщо шуканий елемент збігся з центральнім, (базовий випадок)
- return middle; //то повернути індекс цього елемента
- else if(a[middle] < key) //якщо шукане більше центрального значення, (рекурсивний випадок)
- return binarySearch(a, middle + 1, right, key, mode); //то рекурсивно викликати функцію змістивши ліву межу пошуку
- else //якщо ж ні, (тобто шукане менше центрального, теж рекурсивний випадок)
- return binarySearch(a, left, middle - 1, key, mode); то рекурсивно викликати функцію змістивши праву межу пошуку
- }
- if(mode == '-') { //якщо масив відсортований в порядку спадання
- int middle = (left + right) / 2; //індекс центрального елемента
- if(key == a[middle]) //якщо шуканий елемент збігся з центральнім, (базовий випадок)
- return middle; //то повернути індекс цього елемента
- else if(a[middle] > key) //якщо шукане менше центрального значення, (рекурсивний випадок)
- return binarySearch(a, middle + 1, right, key, mode); //то рекурсивно викликати функцію змістивши ліву межу пошуку
- else //якщо ж ні, (тобто шукане менше центрального, теж рекурсивний випадок)
- return binarySearch(a, left, middle - 1, key, mode); //то рекурсивно викликати функцію змістивши праву межу пошуку
- }
- } else //якщо границі зімкнулись, але функція не повернула значення індексу(тобто шуканого елемета немає в масиві)
- return -1; //то повернути -1 (неможливе для індексу значення)
- }
Add Comment
Please, Sign In to add comment