to midand the other going from mid to rightwhere mid is the position half way from lef to rightand whereinitiallylef and right are the leftmost and rightmost positions of the array because the array is sortedit is easy to see which of each pair of segments the searched-for item is inand the search can then be restricted to that segment moreoverbecause the size of the sub-array going from locations lef to right is halved at each iteration of the while-loopwe only need log steps in either the average or worst case to see that this runtime behaviour is big improvementin practiceover the earlier linear-search algorithmnotice that log is approximately so that for an array of size only iterations are needed in the worst case of the binary-search algorithmwhereas are needed in the worst case of the linear-search algorithm with the binary search algorithmit is not so obvious that we have taken proper care of the boundary condition in the while loop alsostrictly speakingthis algorithm is not correct because it does not work for the empty array (that has size zero)but that can easily be fixed apart from thatis it correcttry to convince yourself that it isand then try to explain your argument-for-correctness to colleague having done thattry to write down some convincing argumentsmaybe one that involves loop invariant and one that doesn' most algorithm developers stop at the first stagebut experience shows that it is only when we attempt to write down seemingly convincing arguments that we actually find all the subtle mistakes moreoverit is not unusual to end up with better/clearer algorithm after it has been modified to make its correctness easier to argue it is worth considering whether linked-list versions of our two algorithms would workor offer any advantages it is fairly clear that we could perform linear search through linked list in essentially the same way as with an arraywith the relevant pointer returned rather than an index converting the binary search to linked list form is problematicbecause there is no efficient way to split linked list into two segments it seems that our array-based approach is the best we can do with the data structures we have studied so far howeverwe shall see later how more complex data structures (treescan be used to formulate efficient recursive search algorithms notice that we have not yet taken into account how much effort will be required to sort the array so that the binary search algorithm can work on it until we know thatwe cannot be sure that using the binary search algorithm really is more efficient overall than using the linear search algorithm on the original unsorted array that may also depend on further detailssuch as how many times we need to performa search on the set of items just onceor as many as times we shall return to these issues later first we need to consider in more detail how to compare algorithm efficiency in reliable manner