2 4 7 10 11 45 50 59 60 66 69 70 79 key>vals[6], As before, find index of middle value: . Then, since: change and call BinarySearch on the list indexed from to low high. ( ) BinarySearch vals= , key=62 Find of middle value: . Then, since key<vals[9] , change ( ) BinarySearch vals= , key=62 Find index of middle value: . Then, since key>vals[7] , change ( ) BinarySearch vals= , key=62 Find index of middle value: . Since low, mid, and high are all the same this indicates that the key is not present. However, when the key is not found, it is customary to return the location where the key would occur if it were inserted into the list. One way to do this is to proceed as we have so far: key>vals[8] , change ( ) BinarySearch vals= , key=62 Now, since , this means that the falls between and . Thus, if the key were to be inserted in the proper order, it would be at index 9 (the 10th element). It is customary for the binary search algorithm to return -10 in this situation (for this example). The negative sign means that the key was not found. This begs the question as to why the method algorithm doesn’t just return -9 since that is the index where it belongs. See the next two examples! Example 3a Suppose we are looking for 2 in the array below. – ( ) , BinarySearch vals= key=2 The method returns 0 because that is the index where the key was found, vals[0]. Example 3b Suppose we are looking for 1 in the (same as previous array) below. –
2 4 7 10 11 45 50 59 60 66 69 70 79 As before, find index of middle value: . Then, since: key>vals[6], change and call BinarySearch on the list indexed from low to high. BinarySearch ( vals= , key=62 ) Find of middle value: . Then, since key<vals[9] , change BinarySearch ( vals= , key=62 ) Find index of middle value: . Then, since key>vals[7] , change BinarySearch ( vals= , key=62 ) Find index of middle value: . Since low, mid, and high are all the same this indicates that the key is not present. However, when the key is not found, it is customary to return the location where the key would occur if it were inserted into the list. One way to do this is to proceed as we have so far: key>vals[8] , change BinarySearch ( vals= , key=62 ) Now, since , this means that the falls between and . Thus, if the key were to be inserted in the proper order, it would be at index 9 (the 10th element). It is customary for the binary search algorithm to return -10 in this situation (for this example). The negative sign means that the key was not found. This begs the question as to why the method algorithm doesn’t just return -9 since that is the index where it belongs. See the next two examples! Example 3a – Suppose we are looking for 2 in the array below. BinarySearch ( vals= , key=2 ) The method returns 0 because that is the index where the key was found, vals[0]. Example 3b – Suppose we are looking for 1 in the (same as previous array) below.
ch18_recursion.docx