I've got a dataset of about 10,000 employee IDs—just integers—and I need to find if a specific ID exists in the system. When I first started coding this, I did what most of us do: I wrote the most obvious solution that came to mind. I didn't think about "algorithms"; I just thought about the goal.

Just looping through the pile

I started with a simple loop. I'll call it a "linear search," though at the time, I just called it "checking every item." Here is how that looked in my editor:

def find_employee(employee_list, target_id):
    for emp_id in employee_list:
        if emp_id == target_id:
            return True
    return False

# Let's test it with a small sample
ids = [102, 455, 321, 890, 112]
print(find_employee(ids, 890)) # True

It works. Perfectly. But as I scaled this up to the full 10,000-record list and started running it inside a loop for a batch report, I noticed a lag. It wasn't a crash, but it felt sluggish. If the ID I'm looking for is at the very end of the list—or not there at all—Python has to check every single element. In the worst case, that's 10,000 checks. Not a dealbreaker for 10k, but if this grows to 10 million? We're in trouble.

Cutting the deck in half

I remembered that if my data is sorted, I don't have to look at every item. I can treat the list like a physical dictionary. I don't start at page one to find "Python"; I open the book in the middle and decide if I need to go left or right.

Let's try to implement a binary search. I'll sort the IDs first, then keep splitting the search area in half. Here was my first attempt at the logic:

def binary_search_attempt(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1
    
    while low < high: # I'll come back to this condition
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

I ran a test case: `binary_search_attempt([10, 20, 30, 40], 40)`. I expected it to return index 3, but it actually returned -1. I stared at the code for a minute and realized my mistake: the while low < high condition. If the target is the very last element, low eventually becomes equal to high, and the loop exits before checking that final element. It's a classic off-by-one error.

Fixing the logic gap

I adjusted the condition to while low <= high. That tiny change ensures that even when the search window narrows down to a single element, we actually check that element before giving up.

def binary_search_fixed(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1
    
    while low <= high:
        mid = (low + high) // 2
        print(f"Checking index {mid}, value {sorted_list[mid]}") # Debugging trace
        
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

ids_sorted = [112, 102, 321, 455, 890] # Wait, this isn't sorted!
ids_sorted.sort() 
print(f"Found at index: {binary_search_fixed(ids_sorted, 890)}")

Now, watch the debug trace. Instead of 5 iterations (linear), it finds the target in about 3. On a list of 10,000 items, linear search might take 10,000 steps; binary search will take, at most, about 14. That is a massive difference in efficiency.

When to use which

You might be wondering why we don't use binary search for everything. Well, look at that ids_sorted.sort() line. Sorting a list takes time—specifically, O(n log n) time. If you only need to search a list once, it's faster to just do a linear search. But if you sort the list once and then perform thousands of searches? Binary search is the only way to go. I usually weigh the "cost of sorting" against the "frequency of searching" before deciding which one to implement.

📋 Practical Task

Build a Product SKU Finder for E-commerce Inventory

You are managing a warehouse inventory system. You have a list of product SKUs (Stock Keeping Units) which are strings of alphanumeric characters. Because the inventory is huge, you need to implement an efficient lookup system.

Your Task:

1. Create a list of at least 10 unsorted SKU strings (e.g., "SKU105", "SKU002", "SKU999", etc.).
2. Implement a function find_sku_index(sku_list, target_sku) that uses a binary search algorithm to find the index of a target SKU.
3. Inside your main code block, you must first sort the list before passing it to your function.
4. Test the function with one SKU that exists in the list and one that does not, printing the resulting index or a "Not Found" message.