Advertisement
Guest User

Untitled

a guest
Nov 19th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. def mBinarySearch(inputList, beg, end):
  2. mid = (beg + end) // 2
  3. if mid + 1 < len(inputList) and inputList[mid] > inputList[mid+1]:
  4. # Точка разрыва найдена
  5. return inputList[mid+1]
  6. if beg >= end:
  7. return None
  8. if inputList[mid] < inputList[0]: # Показывает, что разрыв произошел до
  9. # середины рассматриваемого участка
  10. return mBinarySearch(inputList, beg, mid - 1)
  11. elif inputList[mid] > inputList[-1]: # Показывает, что разрыв произошел
  12. # после середины рассматриваемого участка
  13. return mBinarySearch(inputList, mid + 1, end)
  14. else: # Нет данных о местоположении точки разрыва относительно середины
  15. # рассматриваемого участка, запуск поиска в двух участках длины n/2
  16. searchBefore = mBinarySearch(inputList, beg, mid - 1)
  17. if searchBefore != None: # Точка разрыва найдена до середины
  18. return searchBefore
  19. searchAfter = mBinarySearch(inputList, mid + 1, end)
  20. if searchBefore == searchAfter: # Оба None - без точки разрыва
  21. return None
  22. else: # Точка разрыва найдена после середины
  23. return searchAfter
  24.  
  25.  
  26. if __name__ == "__main__":
  27. psList = list(map(int, input().split()))
  28. # Назовём i из условия "точкой разрыва"
  29. result = mBinarySearch(psList, 0, len(psList) - 1)
  30. if result == None: # Защита алгоритма на случай, где точка разрыва
  31. # в самом начачле массива (массив полностью отсортирован)
  32. print(psList[0])
  33. else:
  34. print(result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement