List Programs: Linear Search and Frequency

List Programs: Linear Search and Frequency

Two programs from the CBSE list of suggested practicals. Linear search compares the key with each element in turn:

def linear_search(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i
    return -1

Frequency of elements: count how often each value occurs. Keep a list of the distinct values in order of first appearance and use count():

nums = [2, 5, 2, 8, 5, 2]
seen = []
for n in nums:
    if n not in seen:
        seen.append(n)
for n in seen:
    print(n, nums.count(n))
# 2 3
# 5 2
# 8 1

This takes time proportional to the length of the list for every distinct value. The dictionary lesson shows a faster way to count in a single pass.

nums = list(map(int, input().split()))
seen = []
# fill seen with the distinct values in order
print(" ".join(f"{n}:{nums.count(n)}" for n in seen))