Опубликовано 5 лет назад по предмету Информатика от nvkim1961

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

Ответ

Ответ дан Аккаунт удален

Допустим, что мы делим массив на две части при помощи операции 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]. Выбираем второй интервал, поиск завершен.
1. Ответ
  
  Ответ дан Baggs
  
  а разве сравнение не будет считаться за шаг?
2. Ответ
  
  Ответ дан Аккаунт удален
  
  Шаг состоит из сравнения и принятия решения по нему. Т.е. по результатам сравнения выбирается нужный интервал и разделяется посерединею Все это и есть один шаг.
3. Ответ
  
  Ответ дан Baggs
  
  запомни) спасибо)
4. Ответ
  
  Ответ дан Аккаунт удален
  
  В бинарном поиске до 2 элементов - 1 шаг, до 4 - два, до 8 - 3, до 16 - 14, до 32 -5 и т.д. по степеням двойки.
5. Ответ
  
  Ответ дан Аккаунт удален
  
  Описка: 16 - 4

Самые новые вопросы

Другие предметы - 4 года назад

Сочинение-рассуждение. прочитайте текст. есть у меня внучка. однажды она говорит: — у веры в субботу день рождения. она

Другие предметы - 4 года назад

Л.н. толстой. как боролся русский богатырь как сказал иван о своей силе? найдите ответ в тексте. запишите.

История - 4 года назад

Кто такой мильтиад и какова его роль в победе над персами?

История - 4 года назад

Какие примеры н. м. карамзин использует для разъяснения пользы новой системы престолонаследия? согласны ли вы с позицией

География - 4 года назад

Дополните схему. она поможет вам лучше усвоить содержание §1.: 1 что изучает география 2 с помощью чего 3 зачем изучают

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

Информация