Searching an Unordered List This is the most basic search problem Problem Description Given a list of elements in no particular order Given a specific element called the KEY Determine if the key is in the list Why search problems Logging on username and password Telephone directory searches Web page retrieval involves searches Sending email and instant messages Unordered List Search Algorithm An algorithm takes input operates on it and produces output What are the inputs Unordered list and key What are the outputs A Boolean value True or False What do we need to worry about Can it be done Is it computable How efficiently can it be done What kind of data structures should we use What kind of search pattern should we use Unordered List Search Algorithm Inputs Number list n Number key Other Data Boolean answer Boolean means the only values allowed are True and False Initialization Assume list n and key are given to us answer False Computation Outputs return answer FOR i 0 to n 1 DO IF list i equals key THEN answer True quit algorithm ELSE ENDIF ENDFOR Unordered List Search Algorithm Is our algorithm any good It is correct precise incremental and can be abstracted so yes Is it efficient We cannot answer until we have a method to determine its cost and compare against other algorithms solving the same problem The cost of an algorithm can be found simply by counting the number of operations that are performed For our purposes an operation is a single assignment comparison or arithmetic operation The cost of our algorithm is shown on the next page in red Unordered List Search Algorithm Inputs Number list n Number key Other Data Boolean answer Boolean means the only values allowed are True and False Initialization Assume list n and key are given to us answer False Computation 1 1 FOR i 0 to n 1 DO IF list i equals key THEN answer True quit algorithm ELSE ENDIF ENDFOR Outputs return answer 1 1 Cost of Unordered List Search Algorithm We have identified 4 operations that add cost to the algorithm 2 of them occur only once the assignments of True and False to the variable answer 2 of them may occur up to n times each due to the loop The total cost is 2n 2 This cost is exact We still aren t ready to compare yet Computer science does not use exact costs but uses approximate costs with a notation called order notation So what order is our search algorithm What is the worst case cost Worst case is we have to look at and compare the entire list Worst case Cost 2n 2 so this is O n Not only do algorithms have a cost but problems do also It can be proven that our algorithm is as efficient as possible for the unordered search problem No algorithm could be less than O n for unordered search Algorithms can be slower or require more operations than necesary so O n2 or worse would not be incorrect just less efficient Searching an Ordered List This is probably the most common problem actual computers are solving in day to day uses Problem Description Given a list of elements in order Given a specific element called the KEY Determine if the key is in the list Functional View Input Number list n Number key Output Boolean answer Function Answer is True if key is in list False otherwise list n key answer Osearch list n key Building the Algorithm An algorithm takes input operates on it and produces output What are the inputs Ordered list and key What are the outputs A Boolean value True or False What do we need to worry about Can it be done Is it computable How efficiently can it be done What kind of data structures should we use What kind of search pattern should we use We can take advantage of structure of the data Its ordered Building the Algorithm We want to make each guess count as much as possible Since the data is ordered we can effectively compare more than one element at a time against the key If the element we are currently interested in is large than the key then so is every element further along in the array We do not have to compare against them In what order should we chose elements from the list 0 1 2 3 4 5 6 7 n 2 n 1 Building the Algorithm The best we can do is to eliminate 1 2 the list at each guess We do this by comparing the key against the middle element of the list Example 0 1 2 3 4 5 6 7 First compare eliminates bottom half Second compare eliminates top half Third compare eliminates top half This element either matches the key or doesn t Either way we re done 14 15 Building the Algorithm We need some flags to remind us wheat part of the list is still interesting to us As we compare the key against the current element we simply move the high low flags to record the result low lowest element in array still of interest to us current element in array currently being compared against the key high highest element in array still of interest to us Using the While Loop How do we tell when we are done In the previous algorithms we always knew how many times we would have to repeat the process Worse case was to look at every element in the list so size of list told us number of loops FOR i 0 to n 1 DO Here we stop when certain conditions are met When the high and low flag point to the same element we are done We cannot predict in advance how long this will take at least in a way that is easily written We will use a While loop instead of a For loop Using the While Loop There are two forms of loops all programming languages support them They both require initial conditions to be set They both rely on Boolean tests to determine when to stop looping They both have to have some description of how the loop varible s change after each loop For Loop FOR i 0 to n DO stuff ENDDO While Loop WHILE test is True DO stuff ENDDO Ordered Search Algorithm Algorithm INPUT Number list n key OTHERS Boolean answer Integer i n Integer low high current INITIALIZATION low 0 high n 1 answer False Ordered Search Algorithm Algorithm COMPUTATION WHILE low high DO current floor of low high 2 IF list current key THEN answer True quit algorithm ENDIF IF list current key THEN low current 1 ELSE high current 1 ENDIF ENDWHILE IF list low key THEN answer True ENDIF OUTPUT return answer Summary of Costs Problem Algorithm Cost Searching Unordered list Searching sequentially through list O n Searching Ordered List Selecting middle element each time O log n Sorting BubbleSort O n2 Problem Cost O n O log n O n log n