Searching Algorithms

20 min In Progress

Learning Objectives

  • Choose between linear and binary search based on whether the data is sorted
  • Implement LinearSearcher and BinarySearcher as reusable OOP classes
  • Apply both to real security examples: port lists, IP blacklists

The Big Picture

Searching means finding whether something is in a collection and where. In security scripting this comes up constantly: is port 4444 in the list of open ports on this host? Is this IP in the known-bad blacklist? Is this CVE ID in the patched list? Two algorithms cover 95% of cases: Linear (works on anything, O(n)) and Binary (lightning fast on sorted data, O(log n)).

Linear Search — Check Every Item

Walk through the list from the beginning, compare each item to the target, return the position if found. Simple. Works on any list, sorted or not. The downside: worst case you look at every element — O(n). Fine for small or unsorted lists; slow for large sorted ones.

class linear_searcher:
    def __init__(self, items):
        self.items = items

    def find(self, target):
        for index, item in enumerate(self.items):
            if item == target:
                return index
        return -1

    def contains(self, target):
        return self.find(target) != -1


# Security example: is a suspicious port in the open-port scan list?
open_ports = [80, 443, 22, 8080, 3389, 4444, 5900]
SUSPICIOUS = {4444, 1337, 31337, 5900}

scanner = linear_searcher(open_ports)

print('Open port audit:')
for port in open_ports:
    flag = ' <- SUSPICIOUS' if port in SUSPICIOUS else ''
    idx = scanner.find(port)
    print(f'  index {idx}: port {port}{flag}')

print(f'\nPort 4444 found: {scanner.contains(4444)}')
print(f'Port 53  found: {scanner.contains(53)}')

Binary Search — Halve the Space

Binary search requires a sorted list. It works by looking at the middle element: if the target is smaller, search the left half; if larger, search the right half. Each comparison cuts the remaining search space in half — O(log n). A million-item sorted blacklist takes at most 20 comparisons.

Binary search silently sorts the input at construction time. The reported index refers to the sorted order, not the original.
class binary_searcher:
    def __init__(self, items):
        self.items = sorted(items)

    def find(self, target):
        low, high = 0, len(self.items) - 1
        while low <= high:
            mid = (low + high) // 2
            if self.items[mid] == target:
                return mid
            elif target < self.items[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return -1

    def contains(self, target):
        return self.find(target) != -1


# Security example: is this IP in the known-bad blacklist?
blacklist = [
    '10.0.0.5', '10.0.0.12', '10.0.0.20', '10.0.0.33',
    '10.0.0.50', '10.0.0.99', '192.168.50.1',
]

checker = binary_searcher(blacklist)

test_ips = ['10.0.0.20', '10.0.0.21', '192.168.50.1', '8.8.8.8']
print('IP blacklist check:')
for ip in test_ips:
    found = checker.contains(ip)
    status = 'BLOCKED' if found else 'ALLOWED'
    print(f'  {ip:18} -> {status}')

print(f'\nList is pre-sorted internally: {checker.items[:4]} ...')

📝 Exercise: CVE Lookup — Linear vs Binary

You have a list of CVE IDs (already sorted). Implement both a linear_searcher and binary_searcher version of a function that checks whether a given CVE is in the patched list. Then count how many comparisons each approach would theoretically need to find the last item in the list (linear = n, binary = log2(n) rounded up).

code.py
Output

            

        

    


    

        ← Back to Chapter