《JAVA OOP开发》英文版 Chapter 10 Sorting and Searching

Sequence of Unsuccessful Search-1 low high mid search( 45) #10 8 4 low+ high 2 2 345678 5 1217233844778490 o W mid hi 38<45-ow=mid+1=5 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 10-11

© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 11 Sequence of Unsuccessful Search - 1 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 45 ) #1 0 8 low high       + = 2 low high mid 38 < 45 low = mid+1 = 5 mid 4

Sequence of Unsuccessful Search -2 low high mid search( 45) #1 #2 05 8 4 8 6 low+ high 2 2345678 44778490 o mid hi high= mid-15+-45< 77 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 10-12

© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 12 Sequence of Unsuccessful Search - 2 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 45 ) #1 0 8       + = 2 low high mid high = mid-1=5 45 < 77 4 mid 6 low high #2 5 8

Sequence of Unsuccessful Search -3 low high mid search( 45) #10 8 4 #25 8 low+ high #35 5 5 2 2 3 4 56 7 8 44 ow high 44<45 low= mid+1=6 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 10-13

© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 13 Sequence of Unsuccessful Search - 3 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 45 ) #1 0 8       + = 2 low high mid 44 < 45 4 #2 5 8 6 low high #3 5 5 mid 5 low = mid+1 = 6

Sequence of Unsuccessful Search-4 low high mid search( 45) #1 8 #2 8 #3 05560 5 465 low+ high 2 #4 5 12345678 Unsuccessful Search high low no more elements to search +- low>high C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10-14

© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 14 Sequence of Unsuccessful Search - 4 5 12 17 23 38 44 77 0 1 2 3 4 5 6 7 8 84 90 low high mid search( 45 ) #1 0 8       + = 2 low high mid 4 #2 5 8 6 #3 5 5 5 high low #4 6 5 Unsuccessful Search no more elements to search low > high

Binary search Routine public int binarysearch( int [] number, int searchvalue nt low gh number length -1, id (low high)/2 hile( low < high & number [mid]!= searchvalue i f(number [mid< searchvalue lo id 1 else //number[mid]> searchvalue high mid -1 mid =(low high)/2: //integer division will truncate if( low high) d= NOT Found i eturn mid: C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10-15

© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 15 Binary Search Routine public int binarySearch ( int[] number, int searchValue ) { int low = 0, high = number.length - 1, mid = (low + high) / 2; while ( low <= high && number[mid] != searchValue ) { if (number[mid] < searchValue) { low = mid + 1; } else { //number[mid] > searchValue high = mid - 1; } mid = (low + high) / 2; //integer division will truncate } if ( low > high) { mid = NOT_FOUND; } return mid; }