Переповнення обраного типу даних
Щоб дізнатися значення в середині масиву, необхідно скласти праве і ліве значення, і розділити на два. Тобто:
Середина масиву = Ліве значення + (Ліве значення – Праве значення)/2
Тут є небезпека переповнення типу даних при операції додавання. Якщо в масиві є значення настільки великих розмірів, доводиться використовувати різні прийоми, щоб уникнути ризику. Нижче представлені стандартні помилки при розробці двійкового пошуку.
Помилки значень
Або помилки на одиницю. Дуже важливо врахувати наступні варіанти:
- Порожній масив.
- Значення відсутня.
- Вихід за межі масиву.
Кілька примірників
Необхідно врахувати, що у разі існування в масиві декількох однакових примірників ключа програма повинна знаходити певний (перший, останній, наступний за ним).
Розберемо реалізації даного алгоритму на мові програмування C плюс плюс. Необхідно враховувати, що двійковий пошук працює тільки з відсортованим масивом! Якщо масив попередньо не відсортувати, то результат обчислень буде невірним.
Нижче наведено код на C ++. Спочатку ініціалізується масив цілочисельних змінних arr, розміром десять. Далі оператор cin в циклі for очікує введення десяти значень від користувача (рядок десять).
У двадцятої рядку програма чекає від користувача введення значення ключа.
Рядки 29 – 35 являють собою реалізований алгоритм бінарного пошуку. У ході виконання програми в змінну mid записується значення середнього елемента за формулою:
Середина масиву (mid) = (Ліве значення (l) + Праве значення (r))/2
Рядком
arr[mid]==key
Перевіряється, дорівнює чи серединное значення значенням ключа. Якщо одно, то значення змінної flag змінюється значення ІСТИНА, тобто задача вирішена.
Якщо ж серединное значення більше значення нашого ключа, то правій частині (змінна r) присвоюється mid. Якщо навпаки, то mid кладеться в r.
Останнє — це перевірка булевої змінної flag.
