Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
SquirrelLeonid
0 / 0 / 0
Регистрация: 02.11.2017
Сообщений: 33
1

Бинарный поиск

05.02.2018, 18:59. Просмотров 745. Ответов 3
Метки нет (Все метки)

Всем доброго времени суток. Помогите разобраться с бинарным поиском. В теории все понятно: С каждым ходом он отсеивает половину элементов, таким образом O(log2 N) с округлением вверх, где N количество элементов списка
Вот как я пытался его реализовать:
Кликните здесь для просмотра всего текста
Python
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
# -*- coding: utf-8 -*-
import random
n = random.randint(1,10)
my_list = []
i = 0
for i in range(0,n):
    a = random.randint(1,10) 
    while a in my_list: # Чтобы не было повторяющихся чисел
        a = random.randint(1,10)
    my_list.append(a)
    my_list.sort()
    
item = random.choice(my_list) # Выбор случайного числа из списка
print "Я загадал ", item
 
low = 0
high = len(my_list) -  1 # Так как нумерация списка начинается с 0: если всего элементов 5, то наивысшим будет 4
 
while low != high: # Пока не останется один элемент
    mid = (low + high) / 2  # Нужно ли делить на 2 чтобы получить ~ средний элемент списка
    guess = my_list[mid] # Попытка угадать
    if guess == item: # Если названное число совпадает с загаданным, то
        print "Твое число", my_list[mid]
        print "Количество попыток ", i
        break
    if guess > item:
        high = mid - 1
    else: 
        low = mid + 1
    i += 1


Количество попыток практически всегда больше чем log2 N.
Иногда программа вообще не выводит какого-то ответа, к примеру: ("Я загадал число", item) а следующая строка, в которой выводится отгаданное число (print "Твое число", my_list[mid]) попросту не выводится.

Объясните пожалуйста где я ошибаюсь.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2018, 18:59
Ответы с готовыми решениями:

Бинарный поиск
Андрей недавно выучил алгоритм бинарного поиска. Этот алгоритм предназначен для поиска числа в...

Бинарный поиск
Выручайте, уважаемые. Андрей недавно выучил алгоритм бинарного поиска. Этот алгоритм...

Задача на бинарный поиск
Решаю такую задачу: На столе в виде прямоугольника N×M лежат карточки, на которых написаны числа....

Бинарный поиск по двум упорядоченным масивам
Подозреваю, что очень глупый вопрос. ...

Бинарный поиск первого элемента, удовлетворяющего условию
Допустим, есть числовой массив, все элементы которого заранее упорядочены по возрастанию. Нужно...

3
Shamil1
Модератор
2269 / 1563 / 352
Регистрация: 26.03.2015
Сообщений: 5,649
05.02.2018, 20:43 2
Цитата Сообщение от SquirrelLeonid Посмотреть сообщение
Объясните пожалуйста где я ошибаюсь.
Бинарный поиск - в отсортированном массиве.
0
SquirrelLeonid
0 / 0 / 0
Регистрация: 02.11.2017
Сообщений: 33
05.02.2018, 20:48  [ТС] 3
Так ведь числа в массиве сортируются по возрастанию в ходе выполнения программы в 11 строке.
0
Shamil1
Модератор
2269 / 1563 / 352
Регистрация: 26.03.2015
Сообщений: 5,649
05.02.2018, 21:01 4
Лучший ответ Сообщение было отмечено SquirrelLeonid как решение

Решение

SquirrelLeonid,
В строке 20 надо использовать целочисленное деление.

Непонятно, зачем к количеству попыток Вы прибавляете длину списка.

Способ генерации списка, мягко говоря, странный.
1
05.02.2018, 21:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2018, 21:01

Однородный бинарный поиск - кто знает его?
Искал данный алгоритм, да вот не нашёл, может у кого есть его реализация? Жду.

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде...

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru