1. Python / Говнокод #22422

    −16

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    import math
arr = list(range(1, 10001))
num = int(input('Число: '))
log = int(math.log2(len(arr)))

lens = int(len(arr)/2)
arr1 = arr[:lens]
arr2 = arr[lens:]

i = 0
while i <= log:
  print('Шаг', i, 'из', log)
  
  if arr1:
    if num == arr1[0]:
      print(arr1[0])
      break
    if num == arr1[-1]:
      print(arr1[-1])
      break
  if arr2:
    if num == arr2[0]:
      print(arr2[0])
      break
    if num == arr2[-1]:
      print(arr2[-1])
      break
      
  if num in arr1:
    len1 = arr1
    arr1 = arr1[:int(len(arr1)/2) if int(len(arr1)/2) == 0 else int(len(arr1)/2+1)] 
    arr2 = len1[int(len(arr1)/2) if int(len(arr1)/2) == 0 else int(len(arr1)/2+1):]
    
  if num in arr2:
    len2 = arr2
    arr2 = arr2[:int(len(arr2)/2) if int(len(arr2)/2) == 0 else int(len(arr2)/2+1)]
    arr1 = len2[int(len(arr2)/2) if int(len(arr2)/2) == 0 else int(len(arr2)/2+1):]
      
  i += 1

    Бинарный поиск, говно?

    Запостил: lols, 21 Февраля 2017

    Комментарии (16) RSS

    • ava cykablyad 21.02.2017 06:34 # +3

      > arr
      > list
      Мне кажется, нас наебали
      Ответить

      • ava bormand 21.02.2017 06:35 # +8

        Ага, питоний list это массив, а не связный список. Гвидо всех наебал.
        Ответить

    • ava bormand 21.02.2017 06:37 # +8

      > if num in arr1
      Ахуенный двоичный поиск.
      Ответить

      • ava guest 21.02.2017 10:22 # 0

        "/2, log2, arr2"
        Ну и где тут не двоичный поиск?
        Ответить

        • ava dxd 21.02.2017 10:30 # +4

          Привет, Сёма.
          Ответить

        • ava inkanus-gray 21.02.2017 11:43 # +5

          Ты знаешь, что под капотом у оператора in и сколько элементов он просканирует, чтобы дать ответ?
          Ответить

        • ava inho 21.02.2017 18:21 # +2

          Это двоичный поиск, но не за log(n)
          Ответить

          • ava dxd 21.02.2017 18:51 # 0

            Это двоичный поиск, внутри которого используется линейный.
            Ответить

            • ava 1024-- 21.02.2017 19:20 # +2

              двоичный * линейный = билинейный color=green
              Ответить

          • ava cykablyad 21.02.2017 19:37 # 0

            Двоичный поиск, с капусткой, но не красный
            Ответить

      • ava dxd 21.02.2017 12:35 # +3

        Это, кстати, хуйня на фоне того, что вверху берутся слайсы от списка. А они не COW.
        Ответить

        • ava inkanus-gray 21.02.2017 13:12 # +1

          То есть в итоге у программы квадратичный расход памяти?
          Ответить

          • ava dxd 21.02.2017 15:13 # 0

            Я не смотрел в кишки питона, но вполне может быть.
            Ответить

          • ava roman-kashitsyn 21.02.2017 15:59 # +1

            > То есть в итоге у программы квадратичный расход памяти?

            А как насчитался квадратичный? Вроде бы каждый раз размер слайса уменьшается вдвое.
            2*N/2 + 2*N/4 + 2*N/8 + ... <= 2*N
            Ответить

    • ava cykablyad 21.02.2017 10:30 # +5

      Я, cykablyad, находясь в здравом уме и твердой памяти, торжественно заявляю:
      говно
      Ответить

    Добавить комментарий