Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def mBinarySearch(inputList, beg, end):
- mid = (beg + end) // 2
- if mid + 1 < len(inputList) and inputList[mid] > inputList[mid+1]:
- # Точка разрыва найдена
- return inputList[mid+1]
- if beg >= end:
- return None
- if inputList[mid] < inputList[0]: # Показывает, что разрыв произошел до
- # середины рассматриваемого участка
- return mBinarySearch(inputList, beg, mid - 1)
- elif inputList[mid] > inputList[-1]: # Показывает, что разрыв произошел
- # после середины рассматриваемого участка
- return mBinarySearch(inputList, mid + 1, end)
- else: # Нет данных о местоположении точки разрыва относительно середины
- # рассматриваемого участка, запуск поиска в двух участках длины n/2
- searchBefore = mBinarySearch(inputList, beg, mid - 1)
- if searchBefore != None: # Точка разрыва найдена до середины
- return searchBefore
- searchAfter = mBinarySearch(inputList, mid + 1, end)
- if searchBefore == searchAfter: # Оба None - без точки разрыва
- return None
- else: # Точка разрыва найдена после середины
- return searchAfter
- if __name__ == "__main__":
- psList = list(map(int, input().split()))
- # Назовём i из условия "точкой разрыва"
- result = mBinarySearch(psList, 0, len(psList) - 1)
- if result == None: # Защита алгоритма на случай, где точка разрыва
- # в самом начачле массива (массив полностью отсортирован)
- print(psList[0])
- else:
- print(result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement