given an arbitrary collection of keysthe only way to determine if search key is present is by examining each element this has (ntime complexity fundamentallybinary search is natural elimination-based strategy for searching sorted array the idea is to eliminate half the keys from consideration by keeping the keys in sorted order if the search key is not equal to the middle element of the arrayone of the two sets of keys to the left and to the right of the middle element can be eliminated from further consideration questions based on binary search are ideal from the interviewers perspectiveit is basic technique that every reasonable candidate is supposed to know and it can be implemented in few lines of code on the other handbinary search is much trickier to implement correctly than it appears--you should implement it as well as write corner case tests to ensure you understand it properly many published implementations are incorrect in subtle and not-so-subtle ways-- study reported that it is correctly implemented in only five out of twenty textbooks jon bentleyin his book "programming pearlsreported that he assigned binary search in course for professional programmers and found that failed to code it correctly despite having ample time (bentley' students would have been gratified to know that his own published implementation of binary searchin column titled "writing correct programs"contained bug that remained undetected for over twenty years binary search can be written in many ways--recursiveiterativedifferent idioms for conditionalsetc here is an iterative implementation adapted from bentley' bookwhich includes his bug def bsearch (ta)lu len( while <um ( / if [mtl elif [ =treturn elseu return - the error is in the assignment ( in line which can potentially lead to overflow this overflow can be avoided by using ( the time complexity of binary search is given by (nt( / cwhere is constant this solves to (no(log )which is far superior to the (napproach needed when the keys are unsorted disadvantage of binary search is that it requires sorted array and sorting an array takes ( log ntime howeverif there are many searches to performthe time taken to sort is not an issue many variants of searching sorted array require little more thinking and create opportunities for missing corner cases searching boot camp when objects are comparablethey can be sorted and searched for using library search functions typicallythe language knows how to compare built-in typese integersstringslibrary classes