Linear search performance r We analyze the successful and unsuccessful searches separately. We count how many times the search value is compared against the array elements r Successful Search o Best Case-1 comparison o Worst Case-N comparisons(N-array size) r Unsuccessful search Best case Worst Case-N comparisons C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10-6
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 6 Linear Search Performance We analyze the successful and unsuccessful searches separately. We count how many times the search value is compared against the array elements. Successful Search Best Case – 1 comparison Worst Case – N comparisons (N – array size) Unsuccessful Search Best Case = Worst Case – N comparisons
Binary search r If the array is sorted then we can apply the binary search technique number 012345678 5 1217233844778490 r The basic idea is straightforward. First search the value in the middle position. If X is less than this value, then search the middle of the left half next. If X is greater than this value, then search the middle of the right half next Continue in this manner. C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10-7
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 7 Binary Search If the array is sorted, then we can apply the binary search technique. number 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 The basic idea is straightforward. First search the value in the middle position. If X is less than this value, then search the middle of the left half next. If X is greater than this value, then search the middle of the right half next. Continue in this manner
Sequence of Successful Search-1 low high mid search( 44) #10 8 4 low+ high 2 2 345678 5 1217233844778490 o W mid hi 38<44→Iow=mid+1=5 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 10-8
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 8 Sequence of Successful Search - 1 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 44 ) #1 0 8 low high + = 2 low high mid 38 < 44 low = mid+1 = 5 mid 4
Sequence of Successful Search -2 low high mid search( 44) #1 #2 05 8 4 8 6 low+ high 2 2345678 44778490 o mid hi high= mid-15+44<77 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 10-9
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 9 Sequence of Successful Search - 2 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 44 ) #1 0 8 + = 2 low high mid high = mid-1=5 44 < 77 4 mid 6 low high #2 5 8
Sequence of Successful Search -3 low high mid search( 44) #10 8 4 #25 8 low+ high #35 5 5 2 2 3 4 56 7 8 44 Successful search! ow high 44=44「mid C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10-10
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 10 Sequence of Successful Search - 3 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 44 ) #1 0 8 + = 2 low high mid 44 == 44 4 #2 5 8 6 low high #3 5 5 mid 5 Successful Search!!