Linear Search

Search an Unsorted List

def linearSearch(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return None

Analysis of running time:

• worst-case: $O(n)$
• best-case: $O(1)$

More efficient linear search:

• put a sentinel in the list to avoid checking i<len(arr) each time

• faster in practice, but only by a constant factor

def linearSearch2(arr, target):
    last, arr[-1] = arr[-1], target
    i = 0
    while arr[i] != target:
        i += 1
    if i < len(arr)-1 or last == target:
        return i
    else:
        return None

​

Recursive Linear Search

def recursiveLinearSearchHelper(arr, target, start, end):
    if start > end:
        return None
    if arr[start] == target:
        return start
    else:
        return recursiveLinearSearchHelper(arr, target, start+1, end)

def recursiveLinearSearch(arr, target):
    # base case
    if arr == []:
        return None
    return recursiveLinearSearchHelper(arr, target, 0, len(arr) - 1)

Search a Sorted List

def linearSearchSorted(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
        if arr[i] > target:
            return None
    return None

Binary Search

Python code #1

def binarySearch(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high)//2
        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return None

Python code #2 Bad!

• arr[:mid] or arr[(mid+1):] takes $O(n)$ time
• $T(n)=O(n \log n)$

def binarySearch(arr, target):
    if len(arr) == 0:
        return None

    mid = len(arr)//2
    if arr[mid] == target: return mid
    elif arr[mid] > target:
        try:
            return binarySearch(arr[:mid], target)
        except TypeError:
            return None
    else:
        try:
            return binarySearch(arr[(mid+1):], target) + mid + 1
        except TypeError:
            return None  

Python code #3

• pass list and indices as parameters
• list never copied, just re-passed
• $T(n)=O(\log n)$

def binarySearchHelper(arr, target, low, high):
    if high < low:
        return None
    mid = (low + high)//2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binarySearchHelper(arr, target, low, mid-1)
    else:
        return binarySearchHelper(arr, target, mid+1, high)

def binarySearch(arr, target):
    n = len(arr)
    if n == 0:
        return None
    else:
        return binarySearchHelper(arr, target, 0, n-1)

Amortized Cost

• n = len(list)
• AMORTIZE cost of the sort over $k$ searches
  1. search: $T(n)=O(kn)$
  2. sort, then binary search: $T(n)=O(n\log n + k\log n)$
• large $k$, SORT time becomes irrelevant (when $k=O(\log n)$, (1) and (2), same rate)