Searching Patterns

Searching is common: find an item in your data.

1) Linear search (simple)

nums = [10, 20, 30, 40]
target = 30
found = target in nums
print(found)

2) Binary search (fast but requires sorted list)

Binary search is like: keep cutting the list in half.

Use bisect:

import bisect

nums = [10, 20, 30, 40, 50]
i = bisect.bisect_left(nums, 30)
print(i)  # 2

3) Best trick: use set/dict when you do many searches

nums = list(range(1000000))
nums_set = set(nums)

print(999999 in nums_set)  # fast

Graph: linear vs binary

flowchart LR
  A[Linear search] --> B[Check 1 by 1]
  C[Binary search] --> D[Half -> half -> half]

Remember

• Linear search is simple but slower for big data
• Binary search is fast but requires sorted data
• For repeated lookups, use set/dict