52 lines
1.4 KiB
Python
52 lines
1.4 KiB
Python
|
"""
|
||
|
|
name: Nicholas Tamassia
|
||
|
|
|
||
|
|
Honor Code and Acknowledgments:
|
||
|
|
|
||
|
|
This work complies with the JMU Honor Code.
|
||
|
|
|
||
|
|
Comments here on your code and submission.
|
||
|
|
"""
|
||
|
|
|
||
|
|
|
||
|
|
def circular_search(in_list: list[int], search_item: int) -> int:
|
||
|
|
|
||
|
|
# * Nest the recursive function to hide the start-end indexing
|
||
|
|
# * from end user, which could introduce bad input (e.g. start > end)
|
||
|
|
# * It also means we don't have to keep passing in_list and search_term over and over again.
|
||
|
|
def recurse(start: int, end: int) -> int:
|
||
|
|
if end - start == 0:
|
||
|
|
return -1
|
||
|
|
if end - start == 1:
|
||
|
|
return start if in_list[start] == search_item else -1
|
||
|
|
|
||
|
|
mid: int = (start + end) // 2
|
||
|
|
|
||
|
|
if in_list[start] <= in_list[mid - 1]:
|
||
|
|
if in_list[start] <= search_item and search_item <= in_list[mid - 1]:
|
||
|
|
return recurse(start, mid)
|
||
|
|
else:
|
||
|
|
return recurse(mid, end)
|
||
|
|
else:
|
||
|
|
if in_list[mid] <= search_item and search_item <= in_list[end - 1]:
|
||
|
|
return recurse(mid, end)
|
||
|
|
else:
|
||
|
|
return recurse(start, mid)
|
||
|
|
|
||
|
|
return recurse(0, len(in_list))
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
# your code here
|
||
|
|
|
||
|
|
in_list: list[int] = list(map(int, input().split()))
|
||
|
|
search_item: int = int(input())
|
||
|
|
|
||
|
|
index = circular_search(in_list, search_item)
|
||
|
|
|
||
|
|
print(index)
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
main()
|