CareerCup

Binary search tree has a complexity of log n because the height of the tree with n elements will be log n.
But you should ask the interviewer whether he needs the complexity of best case or worst case because for worst case binary search tree takes O(n).

Sorry, worst case binary search is O(log n), not O(n).
Binary search (not to be confused with binary search tree) takes an array of sorted elements, and return the element or an array index of when the element is found (null or -1 if not found).

A binary search starts in the middle of the array, and asks whether the item to find is larger or smaller than the item in the middle of the array.
If smaller, the search will know that the result is to be found in the lower half of the array, if larger, the upper half. This determines a new search range in terms of which array positions we should search: If the item we want to find is smaller than the element in the middle of the array, we know that there is no point in ever considering the elements at a position above the middle. So we repeat the search with the new smaller range (half of the original range) and terminate when the item is found or when there is no more range to search. More details can be found in a heap of CS textbooks or online.
From this description, one can see that a binary search is never going to be O(n), since it will never consider more than half of the values in the array range it currently deals with. (A binary search tree may take O(n) for a worst-case sarch, as the depth of the tree may be O(n), which happens if the keys are inserted in already-sorted order. That is a different matter, and has no relevance to the (array) binary search algorithm.)

This type of question is very basic, and can be translated into "do you have a CS degree? Did you sleep during the lessons?".

Durimg 7 years of programming employment, I've never had cause to implement a binary search. For that matter, I have hardly had use for more than 10% of the stuff I learned durimg my CS master degree.

Interview questions in general are best approaced as school exams: Nobody seriously believes that anyone in 'real life' will complain if you don't know who killed the leader of the French revolution, but it may still be necessary to know in order to get your history exam.
Likewise, nobody expects that you will implement a binary search yourself: It is very basic stuff, and most languages have libraries to do it. But as for school exams, it may (apprently) be required to know binary search to get the job.

As for most other questions during an interview, the questions do not describe what you are going to work with. The interviewers have a few hours to find out whether what you know is appropriate for what they are looking for. The 'real' answer cannot be found in a few hours, so interviewers stage it as an exam: If you do not know A (which we actually don't care about, but it's simple and quick to ask and reply), you probably do not know B, C or D either (which we do care about, but which are too time consuming to judge in an interview.)

If you think you already know B, C and D, your best bet would probably be to show them an application you created that proves it. (Give them links or executables. They will probably ask for details to verify that you actually did create it, or at least that you would have been able to. Just to check for the case where you bring MS Word and claim that you wrote it all by yourself in a weekend :)

Otherwise, if you have problems with this kind of questions, I recommend getting hold of a few textbooks for basic CS courses, and read up on standard CS problems.

please elabrate this