Бинарный поиск (реализация на С++)

C++   4 Апрель 2012  Автор статьи:  

В данной статье я реализую алгоритм бинарного поиска для массива int длины NMAX. Метод binary_search будет возвращать индекс элемента, если он существует и -1 в противном случае. Функции binary_search передается на вход три параметра:

  1. x — элемент, поиск которого производится в массиве.
  2. l (left) — левая граница поиска
  3. r (right) — правая граница поиска
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>
#define NMAX 10
using namespace std;
int a[NMAX];

int binary_search(int x, int l ,int r)
{
    while(r - l > 1)
    //пока результат не станет однозначным
    {
        int mid = (l + r) / 2;
        //делим отрезок [l,r] пополам
        if(a[mid]<x)
        //првоеряем где находимся
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    //цикл нужен, чтобы не править код
    //в случае увелечения интервала
    //[l,r]
    for(int i = l; i <= r; i++)
        if(a[i]==x)
            return i;
    return -1;// не нашли такого элемента

}
int main()
{
       
    for(int i = 0; i < NMAX; i++)
    {
        a[i] = rand();
    }
    sort(a, a + NMAX);
    cout << binary_search(a[5],0,NMAX-1);
    return 0;
}

Поиск для примера осуществлялся в случайном массиве.

Научиться программировать

  • на Delphi

  • на Java

  • на C++