Прикреплённый файл «2012-11-16.binpoisk.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 Ввести отсортированный список чисел и ещё одно число; проверить, содержится ли это число в списке (вручную :) )
5 Как можно воспользоваться свойством упорядоченности списка, чтобы уменьшить количество проверок?
6 '''
7
8 # функции input() можно скармливать что-то вроде range(1,100,3) — будет работать
9 l = input("Введите список чисел: ")
10 print l
11 n = input("Введите число для поиска: ")
12 # Если просто сравнивать элементы один за другим, то
13 # если число есть в списке, придётся просмотреть в среднем его половину,
14 # а если числа нет в списке — то весь :(
15
16 # Но список упорядоченный, следовательно:
17 # Когда искомое число меньше какого-либо элемента списка, то
18 # если оно и встревается, то ближе к началу, чем этот элемент
19 # (а если больше, то — к концу)
20
21 b, e = 0, len(l) # границы поиска
22 while b<e:
23 m = (b+e)/2
24 print "\t",b,e,m
25 if l[m]==n:
26 print "Найдено в", m
27 break
28 if l[m]>n:
29 b, e = b, e-(e-b+1)/2 # Сдвинем правую границу влево
30 else:
31 b, e = b+(e-b+1)/2, e # Сдвинем левую границу вправо
32 else:
33 print "Не найдено"
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2012-11-22 23:35:58, 1.7 KB) [[attachment:2012-11-16.binpoisk.py]]
- [получить | показать] (2012-11-22 23:35:45, 1.3 KB) [[attachment:2012-11-16.sort.py]]
- [получить | показать] (2012-11-22 23:36:17, 0.5 KB) [[attachment:2012-11-16.summacifr-dumb.py]]
- [получить | показать] (2012-11-22 23:36:33, 1.0 KB) [[attachment:2012-11-16.summacifr-nonr.py]]
Вам нельзя прикреплять файлы к этой странице.