Sequential Search Algorithm
Python Programming
Objectives ---------- * sequential search - design, analyze, implement, test, time * continue practicing previously learned skills: algorithm analysis, graphing with theoretical prediction curves Implementation -------------- Write a function named sequential_search. It must have two parameters, a list to search and a value to search for. It must return either the index of the value within the list or -1 if the value is not found in the list. Your search function should NOT print anything. If you have debugging or testing print statements in the function, comment them out before doing any timing. Testing ------- Create a list of five random numbers. Use randint, don't hardcode. Demonstrate your algorithm finding each of the numbers. in the list. Then look for a number not in the list. You may write a testing function if you wish, params and returns up to you, or do all testing in the main program. expected output (use different numbers than in the example) numbers [5, 8, 3, 11, -2] searching for 5 expected index: 0 returned index: 0 test passed: YES searching for 8 expected index: 1 returned index: 1 test passed: YES searching for 3 expected index: 2 returned index: 2 test passed: YES searching for 11 expected index: 3 returned index: 3 test passed: YES searching for -2 expected index: 4 returned index: 4 test passed: YES searching for 100 expected index: -1 returned index: -1 test passed: YES passed 6 out of 6 tests Timing ------ Make sure you are timing the WORST CASE for sequential search. That means look for a value you know is not in the list. Do NOT include list creation in your timing. Do NOT include any input. Only time sequential search. If you laptop is very fast, you might have to time many calls to sequential search, not just one call. To get the time for just one call, divide by the number of calls. example: repetition_count = 10000 time_start = time() for rep in range( repetition_count ): ind = sequential_search( value, my_list ) time_end = time() time_all_reps = time_end - time_start time_one_rep = time_all_reps / repetition_count You may create the timing table in your program so you don't have to type it up in Word. If you do that, your table must have neat columns that line up and 3 or 4 significant figures after leading zeros. example: list single comparison time length search time or C estimate 2000 0.000205 1.025e-07 4000 0.0004391 1.098e-07 6000 0.0006798 1.133e-07 8000 0.0008866 1.108e-07 10000 0.001112 1.112e-07