looking for the search generally does not start at the middle of the dictionary person looking for word starting with 'sgenerally assumes that entries beginning with 'sstart about three quarters of the way through the dictionary thushe or she will first open the dictionary about three quarters of the way through and then make decision based on what they find as to where to look next in other wordspeople typically use some knowledge about the expected distribution of key values to "computewhere to look next this form of "computedbinary search is called dictionary search or interpolation search in dictionary searchwe search at position that is appropriate to the value of as follows pk [ [nl[ the location of particular key within the key range is translated into the expected position for the corresponding record in the tableand this position is checked first as with binary searchthe value of the key found eliminates all records either above or below that position the actual value of the key found can then be used to compute new position within the remaining range of the table the next check is made based on the new computation this proceeds until either the desired record is foundor the table is narrowed until no records are left variation on dictionary search is known as quadratic binary search (qbs)and we will analyze this in detail because its analysis is easier than that of the general dictionary search qbs will first compute and hen examine [dpneif [dpnethen qbs will sequentially probe by steps of size nthat iswe step through [dpn ne] until we reach value less than or equal to similarly for [dpnewe will step forward by until we reach value in that is greater than we are now within positions of assume (for nowthat it takes constant number of comparisons to bracket within sublist of size we then take this sublist and repeat the process recursively what is the cost for qbsnote that cn cn/ and we will be repeatedly taking square roots of the current sublist size until we find the item we are looking for because log and we can cut log in half only log log timesthe cost is th(log log nif the number of probes on jump search is constant the number of comparisons needed is = ip(need exactly probes