Attachment '2012-11-16.binpoisk.py'

Download

   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 "Не найдено"

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.