Transcription
ge
Algorithm Awell- dofproblem. roblems– Sor;ng– Searching–
Euclid'salgorithmforgreatestcommondivisor Problem:– FindthegreatestcommondivisoroftwonumbersAandB GCDAlgorithm1. WhileBisnotzero,repeatthefollowing: IfA B,thenA A- ‐BOtherwise,B B- ‐A2. AistheGCDint A 40902;int B 24140;print("GCD of " A " and " B " is ");while (B ! 0) {if (A B) {A A - B;} else {B B - A;}}println(A);
Exhaus ve(Linear)Search– ovaluebeingsought– eachiteminthearrayFind JKLM NOPQRSTUVW X
Exhaus ve(Linear)Search// Search for a matching String val in the array vals.// If found, return index. If not found, return -1.int eSearch(String val, String[] vals) {// Loop over all items in the arrayfor (int i 0; i vals.length; i ) {// Compare itemsint rslt val.compareTo( vals[i] );if ( rslt 0 ) {return i;}// Found it// Return index}return -1;}// If we get this far, val was not found.
BinarySearch Quicklyfindanitem(val)inasortedlist. hestindexRepeatwhilemin Ifvalcomesbeforemiddle,thenresetmaxtomiddle- ‐1Ifvalcomesahermiddle,resetmintomiddle 1Ifmin max,valnotfoundThe most efficient way to play "guess the number"
BinarySearchFind JKLM NOPQRSTUVW X
// Search for a matching val String in the String array vals// If found, return index. If not found, return -1// Use binary search.int bSearch(String val, String[] vals) {int min 0;int max vals.length-1;int mid;int rslt;while (min max) {mid int( (max min)/2 );// Compute next indexrslt val.compareTo( vals[mid] );// Compare valuesif ( rslt 0 ) {return mid;} else if ( rslt 0 ) {max mid - 1;} else {min mid 1;}////////////}// If we get this far, val was not found.return -1;}Found itReturn indexval is before vals[mid]Reset max to item before midval is after vals[mid]Reset min to item after mid
AnExperiment- ‐Exhaus vevs.BinarySearch Fornames(Strings)inarraysofincreasingsize tera;onsforeachagainstlistsize Startwithanarrayof3830 names(Strings)
Wow! That's fast!
WorstCaseRunningTime a ons N(wemustlookateveryitem) N/8itemsremain(N/23) Searchstopswhenitemstosearch(N/2K) 1i.e.N 2K,log2(N) KWorstcase:Numberofitera algorithmandexecutesinO(logN):me.
K 35004000
K 35004000
BinarySearch Quickly#find#an#item#(val)#in#a sorted#list.# Procedure: 1. Init min#and#max#variables#to#lowestand#highestindex# 2. Repeatwhile# min# #max a. Compare#item#atthe# middleindex#with#thatbeing#sought(val) b. If#item#at middleequals#val,#return#middle# c.
