Информатика • 9 класс
108

Двоичный поиск в массиве (C++)

  • Двоичный (бинарный) поиск — метод поиск элементов в отсортированном массиве путём деления его на две части.

 

  • Пример. Найдём индекс ячейки, в которой хранится число 4.

    Решение.

Индекс

0

1

2

3

4

5

6

7

8

9

10

11

Массив

1

2

3

4

5

6

7

8

9

10

11

12

    • ищем средний элемент при деления массива на 2 части (0 + 11) / 2 = 5 (округление вниз). Элемент с индексом 5 больше искомого числа. Следовательно, проверяем первую половину массива;

Индекс

0

1

2

3

4

5

6

7

8

9

10

11

Массив

1

2

3

4

5

6

7

8

9

10

11

12

    • ищем средний элемент первой половины массива (0 + 4) / 2 = 2. Элемент с индексом 2 меньше искомого числа. Следовательно, рассматриваем вторую половину массива;

Индекс

0

1

2

3

4

5

6

7

8

9

10

11

Массив

1

2

3

4

5

6

7

8

9

10

11

12

    • ищем средний элемент второй половины массива (3 + 4) / 2 = 3. Элемент с индексом 3 равен искомому элементу.

Индекс

0

1

2

3

4

5

6

7

8

9

10

11

Массив

1

2

3

4

5

6

7

8

9

10

11

12

    • Ответ. Число 4 хранится в ячейке с индексом 3.
Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»