# PracProg2searchsort

1.

**While loop version:**

def linear_search(lst, value): """ (list, object) -> int Return the index of the last occurrence of value in lst, or return -1 if value is not in lst. >>> linear_search([2, 5, 1, -3], 5) 1 >>> linear_search([2, 4, 2], 2) 2 >>> linear_search([2, 5, 1, -3], 4) -1 >>> linear_search([], 5) -1 """ i = len(lst) - 1 # The index of the next item in lst to examine. # Keep going until we reach the end of lst or until we find value. while i != -1 and lst[i] != value: i = i - 1 # If we fell off the end of the list, we didn't find value. if i == -1: return -1 else: return i

**For loop version:**

def linear_search(lst, value): """ (list, object) -> int Return the index of the last occurrence of value in lst, or return -1 if value is not in lst. >>> linear_search([2, 5, 1, -3], 5) 1 >>> linear_search([2, 4, 2], 2) 2 >>> linear_search([2, 5, 1, -3], 4) -1 >>> linear_search([], 5) -1 """ # The first index is included, the second is not, and the third is the # increment. for i in range(len(lst) - 1, -1, -1): if lst[i] == value: return i return -1

**Sentinal version:**

def linear_search(lst, value): """ (list, object) -> int Return the index of the last occurrence of value in lst, or return -1 if value is not in lst. >>> linear_search([2, 5, 1, -3], 5) 1 >>> linear_search([2, 4, 2], 2) 2 >>> linear_search([2, 5, 1, -3], 4) -1 >>> linear_search([], 5) -1 """ # Add the sentinel at the beginning. lst.insert(0, value) i = len(lst) - 1 # Keep going until we find value. while lst[i] != value: i = i - 1 # Remove the sentinel. lst.pop(0) # If we reached the beginning of the list we didn't find value. if i == 0: return -1 else: # When we inserted, we shifted everything one to the right. Subtract 1 # to account for that. return i - 1

2.

If there are duplicates, the one at the highest index is found.

3.

The question asks **roughly** how many times we need to search in order to make sorting the list first (on the order of N log_2 N steps) and then using binary search (on the order of log_2 N steps) faster than than just using linear search (on the order of N steps).

If there are k searches, then using linear search takes on the order of k * N steps.

It takes N log_2 N steps to sort a list with N items. In addition to the sorting time, there are all the binary searches to account for, each taking log_2 N steps, so this approach takes on the order of N log_2 N + k * N log_2 N steps.

N log_2 N + k * log_2 N < k * N [subtract k * log_2 N from both sides] N log_2 N < k * N - k * log_2 N [simplify] N log_2 N < k * (N - log_2 N) [divide both sides by (N - log_2 N)] (N log_2 N) / (N - log_2 N) < k [N is much larger than log_2 N, so we simplify the denominator and multiply the numerator by 2 -- remember, we want a rough answer:] (2 * N log_2 N) / N < k [simplify] 2 * log_2 N < kThe actual threshold is slightly smaller, but this is a fine rough estimate.

## Page History

- V17: Paul Gries [almost 4 years ago]
- V16: Paul Gries [almost 4 years ago]
- V15: Paul Gries [almost 4 years ago]
- V14: Paul Gries [almost 4 years ago]
- V13: Paul Gries [almost 4 years ago]
- V12: Paul Gries [almost 4 years ago]
- V11: Paul Gries [almost 4 years ago]
- V10: Paul Gries [almost 4 years ago]
- V7: Paul Gries [almost 4 years ago]
- V9: System [almost 4 years ago]