Дан массив А[7, 8, 12, 16, 18, 20, 30, 38, 49, 50], отсортированный в порядке неубывания...

Question

Дан массив А[7, 8, 12, 16, 18, 20, 30, 38, 49, 50], отсортированный в порядке неубывания чисел. Сколько шагов необходимо для нахождения целого числа x=18 методом бинарного поиска?

Comments

отсортированный в порядке неубывания чисел. Да он и так в порядке неубывания. 5 шагов необходимо сделать точнее цикл, который только на 5 кругу определит x=18

Answer 1

Допустим, что мы делим массив на две части при помощи операции div, т.е. целочисленного деления с недостатком.
1й шаг. [7,8,12,16,18] и [20,30,38,49,50]. Выбираем первый интервал.
2й шаг. [7,8] и [12,16,18]. Выбираем второй интервал.
3й шаг. [12] и [16,18]. Выбираем второй интервал.
4й шаг[16] и [18]. Выбираем второй интервал, поиск завершен.

Comments

эм.. а как программа определит в какой части находилось число 18?

---

Проверив последний элемент

---

Т.е. либо проверяем последний элемент первого интервала, либо первый элемент второго.

---

В нашем случае проверив 18 улучшенный алгоритм сразу бы остановился.

---

Но стандартный проверяет на "меньше либо равно"

---

а разве сравнение не будет считаться за шаг?

---

Шаг состоит из сравнения и принятия решения по нему. Т.е. по результатам сравнения выбирается нужный интервал и разделяется посерединею Все это и есть один шаг.

---

запомни) спасибо)

---

В бинарном поиске до 2 элементов - 1 шаг, до 4 - два, до 8 - 3, до 16 - 14, до 32 -5 и т.д. по степеням двойки.

---

Описка: 16 - 4