Searching: Linear, Binary, Hashing

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

data = [8, -4, 7, 17, 0, 2, 19]
print('17 found at index', linear_search(data, 17))
print('5 found at index', linear_search(data, 5))

def binary_search(lst, key):
    low, high = 0, len(lst) - 1
    step = 0
    while low <= high:
        mid = (low + high) // 2
        step += 1
        print('Step', step, ': low', low, 'high', high, 'mid', mid, '->', lst[mid])
        if lst[mid] == key:
            return mid
        elif key > lst[mid]:
            low = mid + 1          # search right half
        else:
            high = mid - 1         # search left half
    return -1

nums = [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]
print('Found at', binary_search(nums, 17))
print('Found at', binary_search(nums, 4))

def count_linear(lst, key):
    c = 0
    for x in lst:
        c += 1
        if x == key:
            break
    return c
def count_binary(lst, key):
    low, high, c = 0, len(lst) - 1, 0
    while low <= high:
        mid = (low + high) // 2; c += 1
        if lst[mid] == key: break
        if key > lst[mid]: low = mid + 1
        else: high = mid - 1
    return c
big = list(range(1, 1001))          # 1..1000 sorted
for k in [1, 500, 1000]:
    print('key', k, '| linear:', count_linear(big, k), '| binary:', count_binary(big, k))

SIZE = 10
table = [None] * SIZE
def h(key):
    return key % SIZE              # hash function: remainder method
for k in [34, 16, 2, 93, 80, 77]:
    table[h(k)] = k
print(table)
def hash_search(key):
    return table[h(key)] == key    # only ONE look-up
print(93, hash_search(93))
print(45, hash_search(45))

# Collision: two keys get the same position
SIZE = 10
print('h(23) =', 23 % SIZE, ' h(43) =', 43 % SIZE)
# Simple fix: chaining – keep a small list at every slot
table = [[] for _ in range(SIZE)]
for k in [23, 43, 15, 33]:
    table[k % SIZE].append(k)
print(table[3], table[5])

# Python dict is a ready-made hash table
phone = {'Asha': '98110', 'Ravi': '98220', 'Neha': '98330'}
name = 'Ravi'
print(name, '->', phone.get(name, 'not found'))
print('Zoya ->', phone.get('Zoya', 'not found'))