Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Двійковий пошук



План:


Введення

Двійковий (бінарний) пошук (також відомий як метод поділу навпіл і дихотомія) - класичний алгоритм пошуку елемента в відсортованому масиві (векторі). Використовується в інформатики, обчислювальної математики і математичному програмуванні.

Окремим випадком двійкового пошуку є метод бисекции, який застосовується для пошуку коренів заданої безперервної функції на заданому відрізку.


1. Пошук елемента відсортовані масиву

Приклад коду на мові програмування Сі для пошуку елемента x в масиві a[n], відсортовані в порядку зростання:

 size_t  first  =  0  ;  / * Перший елемент в масиві * /  size_t  last  =  n  ;  / * Елемент у масиві, наступних за останнім * /  / * Якщо проглядається ділянка непорожній, first  size_t  mid  ;  if  (  n  ==  0  )  {  / * Масив порожній * /  }  else  if  (  a  [  0  ]  >  x  )  {  / * Не знайдено, а коли вам треба вставити його із зсувом - то в позицію 0 * /  }  else  if  (  a  [  n  -  1  ]  <  x  )  {  / * Не знайдено, а коли вам треба вставити його із зсувом - то в позицію n * /  }  while  (  first  <  last  )  {  / * УВАГА! На відміну від більш простого (first + last) / 2, цей код стійкий до переповнення. Якщо first і last знакові, можливий код (unsigned) (first + last)>> 1. * /  mid  =  first  +  (  last  -  first  )  /  2  ;  if  (  x  <=  a  [  mid  ]  )  {  last  =  mid  ;  }  else  {  first  =  mid  +  1  ;  }  }  / * Якщо перевірка n == 0 на початку опущена - значить, тут розкоментувати! * /  if  (  / * N! = 0 & & * /  a  [  last  ]  ==  x  )  {  / * Бажаємий елемент знайдений. last - шуканий індекс * /  }  else  {  / * Бажаємий елемент не знайдений. Але якщо вам раптом треба його вставити із зсувом, то його місце - last. * /  } 

Незважаючи на те, що код досить простий, в ньому є кілька пасток.

  • Що буде, якщо first і last окремо вміщаються в свій тип, а first+last - ні?
  • Чи буде працювати на порожньому масиві ( n=0)?
  • Чи здатний код знаходити відсутні значення? У деяких програмістів написаний "з листа" двійковий пошук в такій ситуації зациклюється - і вони цього не усвідомлюють, поки тестування не дасть помилку.
  • Іноді потрібно, щоб, якщо x в ланцюжку існує в кількох примірниках, знаходило не будь, а обов'язково перший (як варіант: останній; наступний за останнім). Дана версія коду в такій ситуації знаходить перший із рівних.

Вчений Йон Бентлі стверджує, що 90% студентів, розробляючи двійковий пошук, забувають врахувати будь-яке з цих вимог. І навіть в код, написаний самим Йоном і ходив з книги в книгу, вкралася помилка: код не стійкий до переповнення [1].


2. Програми

Практичні додатки методу двійкового пошуку різноманітні:

  • Широке поширення в інформатики стосовно пошуку в структурах даних. Наприклад, пошук в масивах даних здійснюється за ключу, присвоєному кожному з елементів масиву (у простому випадку сам елемент є ключем).
  • Також його застосовують як чисельного методу для знаходження наближеного рішення рівнянь.
  • Метод бисекции використовується для пошуку чисельних рішень рівнянь.
  • Метод використовується для знаходження екстремуму цільової функції і в цьому випадку є методом умовної одномірної оптимізації. Коли функція має речовий аргумент, знайти рішення з точністю до ε можна за час log 2 1 / ε . Коли аргумент дискретний, і спочатку лежить на відрізку довжини N, пошук рішення займе 1 + \ log_2N \! часу. Нарешті, для пошуку екстремуму, скажімо для визначеності мінімуму, на черговому кроці відкидається той з кінців розглянутого відрізка, значення в якому максимально.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Двійковий код
Двійковий файл
Пошук
Повнотекстовий пошук
Пошук в ширину
Пошук пересічень
Пошук шляху
Пошук з поверненням
Трійчастий пошук
© Усі права захищені
написати до нас
Рейтинг@Mail.ru