sec searching unsorted and sorted arrays let pi be the probability that is in position of when is not in lsequential search will require comparisons let be the probability that is not in then the average cost (nwill be (nnp ipi = what happens to the equation if we assume all the pi ' are equal (except ) (np ip = = ( ( ( depending on the value of + < ( < for large collections of records that are searched repeatedlysequential search is unacceptably slow one way to reduce search time is to preprocess the records by sorting them given sorted arrayan obvious improvement over simple linear search is to test if the current element in is greater than if it isthen we know that cannot appear later in the arrayand we can quit the search early but this still does not improve the worst-case cost of the algorithm we can also observe that if we look first at position in sorted array and find that is biggerthen we rule out positions as well as position because more is often betterwhat if we look at position in and find that is bigger yetthis rules out positions and with one comparison what if we carry this to the extreme and look first at the last position in and find that is biggerthen we know in one comparison that is not in this is very useful to knowbut what is wrong with this approachwhile we learn lot sometimes (in one comparison we might learn that is not in the list)usually we learn only little bit (that the last element is not kthe question then becomeswhat is the right amount to jumpthis leads us to an algorithm known as jump search for some value jwe check every 'th