binary search in this sectionwe describe classic recursive algorithmbinary searchthat is used to efficiently locate target value within sorted sequence of elements this is among the most important of computer algorithmsand it is the reason that we so often store data in sorted order (as in figure figure values stored in sorted order within an indexable sequencesuch as python list the numbers at top are the indices when the sequence is unsortedthe standard approach to search for target value is to use loop to examine every elementuntil either finding the target or exhausting the data set this is known as the sequential search algorithm this algorithm runs in (ntime ( linear timesince every element is inspected in the worst case when the sequence is sorted and indexablethere is much more efficient algorithm (for intuitionthink about how you would accomplish this task by hand!for any index jwe know that all the values stored at indices are less than or equal to the value at index jand all the values stored at indices are greater than or equal to that at index this observation allows us to quickly "home inon search target using variant of the children' game "high-low we call an element of the sequence candidate ifat the current stage of the searchwe cannot rule out that this item matches the target the algorithm maintains two parameterslow and highsuch that all the candidate entries have index at least low and at most high initiallylow and high we then compare the target value to the median candidatethat isthe item data[midwith index mid (low high)/ we consider three casesif the target equals data[mid]then we have found the item we are looking forand the search terminates successfully if target data[mid]then we recur on the first half of the sequencethat ison the interval of indices from low to mid if target data[mid]then we recur on the second half of the sequencethat ison the interval of indices from mid to high an unsuccessful search occurs if low highas the interval [lowhighis empty