Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
wwmax
1 / 1 / 0
Регистрация: 25.10.2018
Сообщений: 289
1

Бинарный и последовательный поиск

10.02.2019, 13:31. Просмотров 1014. Ответов 3
Метки нет (Все метки)

Бинарный поиск. Найдите значения N, для которых бинарный поиск в массиве целых чисел размером N становится в 10, 100 и 1000 раз быстрее последовательного поиска. Вычислите эти значения аналитически и проверьте их экспериментально.

Бинарный поиск:
Python
1
2
3
4
5
6
7
def binSearch(a, x, l, r):
  while l < r-1:
    m = (l+r)//2
    if a[m] > x:
      r = m
    else: l = m
return l if a[l] == x else -1
Последовательный поиск:
Python
1
2
3
4
5
6
7
8
9
10
def search(x):
 nX = -1
 for i in range(n):
   if a[i]==x:
     nx = i
     break
 if nX>=0:
  print(“Нашли под номером ”,nX)
 else:
  print(“Не нашли”)
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2019, 13:31
Ответы с готовыми решениями:

Последовательный поиск
Измените логику Search, так, чтобы находились все совпадения. Изменится ли временная оценка работы...

Как прописать последовательный поиск по DataFrame с условием?
Добрый день, подскажите ПЛИЗ: Смысл- надо вывести значение соответствующего столбца B и умножить...

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

Бинарный поиск
Уважаемые форумчане, правильно ли я понял алгоритм бинарного поиска? # -*- coding: utf-8 -*-...

3
Dax
Модератор
848 / 252 / 91
Регистрация: 23.03.2014
Сообщений: 1,553
Завершенные тесты: 1
13.02.2019, 20:39 2
wwmax, Вам что, отступы ставить жалко, код без этого не работает?
Бмнаренный поиск
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
from random import randint
 
# Создание списка,
# его сортировка по возрастанию
# и вывод на экран
a = []
for i in range(15):
    a.append(randint(1, 50))
a.sort()
print(a)
 
# искомое число
value = int(input())
 
mid = len(a) // 2
low = 0
high = len(a) - 1
 
while a[mid] != value and low <= high:
    if value > a[mid]:
        low = mid + 1
    else:
        high = mid - 1
    mid = (low + high) // 2
 
if low > high:
    print("No value")
else:
    print("ID =", mid)
Добавлено через 17 минут
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def ls(alist,item):
    pos=0
    w=False
    while pos<len(alist):
        if alist[pos]==item:
            w=True
        else:
            pos+=1
    return w
if __name__ == '__main__':
    testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
    print(ls(testlist, 3))
    print(ls(testlist, 13))
Последоватетльный
0
Vik1002
0 / 0 / 0
Регистрация: 12.02.2019
Сообщений: 24
14.02.2019, 10:30 3
В тему бинарного поиска.
Кто-нибудь может подсказать, если считать бинарные числа-это числа, которые представляют собой степень двойки-1,2,4,8..., то как можно через for и if определить является ли число i=8 бинарным. Я думаю сделать диапазон
for i in range(0,i+1):
а далее использовать условие if, но как через него сделать вывод "Да" при условии, что число является степенью двойки.
Если у кого-то есть идеи, то поделитесь)

Добавлено через 16 секунд
В тему бинарного поиска.
Кто-нибудь может подсказать, если считать бинарные числа-это числа, которые представляют собой степень двойки-1,2,4,8..., то как можно через for и if определить является ли число i=8 бинарным. Я думаю сделать диапазон
for i in range(0,i+1):
а далее использовать условие if, но как через него сделать вывод "Да" при условии, что число является степенью двойки.
Если у кого-то есть идеи, то поделитесь)
0
dondublon
4078 / 1547 / 292
Регистрация: 17.03.2012
Сообщений: 8,462
Записей в блоге: 5
14.02.2019, 10:36 4
Бинарный поиск имеет сложность O(log(n)), последовательный, соответственно, O(n). Логарифм можно брать по основанию 2, но вообще тут есть свои помехи.
Так что решаете уравнение 10 (100, 1000, etc)*log2(n)=n и вуаля. Потом проверить экспериментально.

Добавлено через 2 минуты
Цитата Сообщение от Vik1002 Посмотреть сообщение
В тему бинарного поиска.
Кто-нибудь может подсказать, если считать бинарные числа-это числа, которые представляют собой степень двойки-1,2,4,8.
Бинарный поиск к числам - степеням двойки отношения не имеет. Это вполне реальная задача, в отличие от "определить, является ли число степенью двойки".
1
14.02.2019, 10:36
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.02.2019, 10:36

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Бинарный поиск
Здравствуйте мне срочно нужен код бинарного поиска и можно с подробным обуснением Заранее...

Последовательный и бинарный поиск
нужно сделать 2 программы: 1)которая осуществляет последовательный поиск(без барьера) дан массив...

Бинарный и последовательный поиск
Бинарный поиск. Найдите значения N, для которых бинарный поиск в массиве целых чисел размером N...

Последовательный/быстрый последовательный поиск
Есть реализация двух методов поиска. По логике быстрый последовательный должен быть быстрее, но...


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

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

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