Updated a year ago
DSA
Use the "Run" button to execute the code.
Binary Search
Here is the general strategy behind binary search, which is applicable to a variety of problems:
- Come up with a condition to determine whether the answer lies before, after or at a given position
- Retrieve the midpoint and the middle element of the list.
- If it is the answer, return the middle position as the answer.
- If answer lies before it, repeat the search with the first half of the list
- If the answer lies after it, repeat the search with the second half of the list.
Here is the generic algorithm for binary search, implemented in Python:
def binary_search(lo, hi, condition):
"""TODO - add docs"""
while lo <= hi:
mid = (lo + hi) // 2
result = condition(mid)
if result == 'found':
return mid
elif result == 'left':
hi = mid - 1
else:
lo = mid + 1
return -1
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # <= because left and right could point to the same element, < would miss it
mid = left+(right-left)//2 # double slash for integer division in python 3, we don't have to worry about integer `left + right` overflow since python integers can be arbitrarily large
# found target, return its index
if arr[mid] == target:
return mid
# middle less than target, discard left half by making left search boundary `mid + 1`
if arr[mid] < target:
left = mid + 1
# middle greater than target, discard right half by making right search boundary `mid - 1`
else:
right = mid - 1
return -1 # if we get here we didn't hit above return so we didn't find target
if __name__ == '__main__':
arr = [int(x) for x in input().split()]
target = int(input())
res = binary_search(arr, target)
print(res)
1 2 3 4 5
3
2
Linked List
A linked list is a data structure used for storing a sequence of elements. It's data with some structure (the sequence).
We'll implement linked lists which support the following operations:
- Create a list with given elements
- Display the elements in a list
- Find the number of elements in a list
- Retrieve the element at a given position
- Add or remove element(s)
- (can you think of any more?)