chap searching element in lthat iswe check elements [ ] [ ]and so on so long as is greater than the values we are checkingwe continue on but when we reach value in greater than kwe do linear search on the piece of length that we know brackets if it is in the list if mj < ( )jthen the total cost of this algorithm is at most -way comparisons thereforethe cost to run the algorithm on items with jump of size is (njm what is the best value that we can pick for jwe want to minimize the cost min + - <= <= take the derivative and solve for ( to find the minimumwhich is in this casethe worst case cost will be roughly this example teaches us some lessons about algorithm design we want to balance the work done while selecting sublist with the work done while searching sublist in generalit is good strategy to make subproblems of equal effort this is an example of divide and conquer algorithm what if we extend this idea to three levelswe would first make jumps of some size to find sublist of size whose end values bracket value ww would then work through this sublist by making jumps of some smaller sizesay finallyonce we find bracketed sublist of size we would do sequential search to complete the process this probably sounds convoluted to do two levels of jumping to be followed by sequential search while it might make sense to do two-level algorithm (that isjump search jumps to find sublist and then does sequential search on the sublist)it almost never seems to make sense to do three-level algorithm insteadwhen we go beyond two levelswe nearly always generalize by using recursion this leads us to the most commonly used search algorithm for sorted arraysthe binary search described in section if we know nothing about the distribution of key valuesthen binary search is the best algorithm available for searching sorted array (see exercise howeversometimes we do know something about the expected key distribution consider the typical behavior of person looking up word in large dictionary most people certainly do not use sequential searchtypicallypeople use modified form of binary searchat least until they get close to the word that they are