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).

alt

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?)