def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
index = None
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
index = midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return (found, index)
testlist = [0, 1, 2, 8, 13, 13, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))
def binarySearchLeft(alist, item):
left = 0
right = len(alist) - 1
found = False
while right - left > 1:
midpoint = (right + left) // 2
if alist[midpoint] >= item:
right = midpoint
else:
left = midpoint
if alist[right] == item:
found = True
else:
right = None
return (found, right)
testlist = [0, 1, 2, 8, 13, 13, 13, 17, 19, 32, 42,]
print(binarySearchLeft(testlist, 3))
print(binarySearchLeft(testlist, 13))
Ссылки по теме
- Курс на codeforces