Register

Hi.i need a correct explanation on binary search..how it will be log n.

• retagged by
412 views

1 Answer

Best answer
4 votes
4 votes
$T(n) = T(n/2) + 1$

This is the recurrence relation as after '1' search we eliminate $n/2$ elements.

Solving we get

$T(n) = T(n/2) + 1 \\= T(n/2^2) + 2 \\= \dots \\=T(n/2^{\lg n}) + \lg n \\= T(1) + \lg n \\= 1 + \lg n$
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,227 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
User Avatar
4 votes
4 votes
1 answer
2
Aghori asked Nov 5, 2017
1,245 views
Binary search on two mutually exclusive arrays.
There are two sorted list each of length $n$ ... the search the moment we find the element. So tell me whose solution is correct? Why my solution should be incorrect?
There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons require...
User Avatar
Link Copied!