it should be obvious that only special kinds of problems can be (log nfor instanceif the input is list of numbersan algorithm must take (nmerely to read the input in thuswhen we talk about (log nalgorithms for these kinds of problemswe usually presume that the input is preread we provide three examples of logarithmic behavior binary search the first example is usually referred to as binary search binary search given an integer and integers an- which are presorted and already in memoryfind such that ai xor return - if is not in the input the obvious solution consists of scanning through the list from left to right and runs in linear time howeverthis algorithm does not take advantage of the fact that the list is sorted and is thus not likely to be best better strategy is to check if is the middle element if sothe answer is at hand if is smaller than the middle elementwe can apply the same strategy to the sorted subarray to the left of the middle elementlikewiseif is larger than the middle elementwe look to the right half (there is also the case of when to stop figure shows the code for binary search (the answer is midas usualthe code reflects ++' convention that arrays begin with index /*performs the standard binary search using two comparisons per level returns index where item is found or - if not found *template int binarysearchconst vector aconst comparable int low high size whilelow <high int mid low high ifamid low mid else ifamid high mid else return mid/found return not_foundfigure binary search /not_found is defined as -