Why Linear Search is Better than Binary Search

On the second day of my Algorithms class, my professor wrote two algorithms on the board:

Linear Search(...)
(Linear search is a process where you iterate through a list from start to finish, and return the result as you find it. Doesn't work so well with large sets of numbers.)

Binary Search(...)
(Binary search is a process where you keep cutting a sorted list in half, until you find the result. It works well with large sets of numbers.)

He paused for a moment, and asked us a fairly simple question:

What's better? Linear Search or Binary Search?

Not only does my professor have a heavy accent, but it seems like he's assaulting you every time he asks a question. We all froze up, and mumbled "binary..?" The thing is, we've been taught to analyze everything through time complexity, and for large data sets, binary search has an obvious advantage. We started thinking more. "Doesn't it depend on how the data is organized?", "It depends on large the data set is!", etc etc.

He solicited responses for a full 7 minutes (he counted), and then said:

What is better anyway? What if you have a stupid boss who doesn't understand complicated code? Maybe you write a nice binary search algorithm and show it to him. He thinks it's wrong because it's complex and he fires you. You see, now linear search is better. At least you still have a job."

Hidden animosity aside, this was a very important lesson to teach. Because we were taught about time complexity, an entire class of students managed to ignore common sense. 

Takeaway: How much would you charge if someone asked you to clean every window in the United States? Why?


Follow me on twitter: @zeteg