i dont get it how can a binary search have more time complexity than linear search!!

I think this is a very general concept — binary searching a space. In a given a search space, you can define a predicate function on some data structure (sorted arrays in the case of a basic lowerbound calculation for example — it can get as complicated a data structure as you want) and an argument (say some positive integer for our sake). The predicate function would output a yes/no answer. The property that the predicate needs to satisfy is that for progressively increasing the argument, the series of answers by the predicate is of the form — No ... No No Yes Yes ... Yes. Now given this series, you can quite easily see that if you are just given this boolean array of outputs, its quite easy to perform a binary search in log(n) time with O(1) query time. But in general, its probably not feasible to get the output array, a more useful thing to do is query the predicate every time on the middle element of your current search space. Now the reason you see these weird complexities is because for each of the log(n) queries that your binary search makes, the calculation of the predicate itself can take more than O(1) complexity. A simple example problem to illustrate a non-O(1) predicate is — Find the number of nodes in a complete binary tree (a binary tree whose every layer but the last have two children, and the last layer’s nodes are to as far left as possible) in less than O(n) time. Here you’d have to notice that the root-leaf path length is O(log(n)) and for each root to leaf path, the predicate finds the answer to — is the path length less than h(the max height of tree)? Hence upon a binary search with O(log(n)) queries and for each query you have an O(log(n)) predicate calculation — the total overall complexity is O(log^2(n))