Search Quest VII: The Search for Search (A Python Story)

Wanting a programming problem to work on but reluctant to tackle a big project, I returned to an old college textbook to look for something challenging but within my pay-grade, so to speak:

Implement sequential search and binary search algorithms on your computer. Run timings for each algorithm on arrays of size n = 10i for i ranging from 1 to as large a value as your computer’s memory and compiler will allow. For both algorithms, store the values 0 through n-1 in order in the array, and use a variety of random search values in the range 0 to n -1 on each size n. Graph the resulting times. When is sequential search faster than binary search for a sorted array? 

In short, for lists of data values in numerical order of varying size, compare on a graph the speeds of two search algorithms, sequential search and binary search.

For the benefit of readers who are not familiar with the said search methods, I’ll use an analogy I once heard during my time as a student at teachers’ college. Imagine you have to find the contact information of someone called “Daryl Daryl” in a telephone directory. First, you search for the name sequentially, that is, starting at the very first name in the phonebook you scan each name one by one until you land on “Daryl Daryl.” This, of course, is not how we would look up someone in real life, but let’s suspend our disbelief for explanation’s sake.

Continue reading “Search Quest VII: The Search for Search (A Python Story)”