Register

Recent questions tagged binary-search

4 votes
4 answers
32
Number of binary search trees
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
User Avatar
4 votes
1 answer
36
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
7 votes
3 answers
38
Self-doubt
Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ? 1. T(n) = 2T(n/2) + 1 2. T(n) = 2T(n/2) + 2 Please specify relevant reasons.
Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ?1. T(n) = 2T(n/2) + 12. T(n) = 2T(n/2) + 2Please specify releva...
User Avatar
10 votes
3 answers
39
Modified Binary Search
Suppose the first step in binary search algorithm is changed to M = (9L+R)/10, we know that the complexity of binary search is log(n). What will be the complexity of modified search? a) log(n) b) n c) n$\log 9/10(n)$ d) 2nlog(n)
Suppose the first step in binary search algorithm is changed to M = (9L+R)/10, we know that the complexity of binary search is log(n). What will be the complexity of modi...
User Avatar
6 votes
5 answers
40
Binary search
How to get space complexity of binary search .. I am getting confusion in Space complexity = ip + extra (stack) And ip = nB ( why it is nB) ????? And extra = logn B So nB+ log n B = O(n) ...
How to get space complexity of binary search ..I am getting confusion in Space complexity = ip + extra (stack) And ip = nB ( why it is nB) ????? And extra = logn B So nB+...
User Avatar
1 votes
1 answer
41
algorithm
A binary search algorithm is implemented using recurrsion then what is the space and time complexity?
A binary search algorithm is implemented using recurrsionthen what is the space and time complexity?
User Avatar
5 votes
4 answers
43
Binary Search
I/p - Sorted array of n element O/p- find any two elements a and b such that (a+b)>1000 if lenear search is possible then go to Binary Search and Find time complexity ..?
I/p - Sorted array of n elementO/p- find any two elements a and b such that (a+b)>1000if lenear search is possible then go to Binary Search and Find time complexity ..?
User Avatar
11 votes
2 answers
44
Self doubt in Binary search Algo
The average successful search time taken by binary search on a sorted array of $10$ items? $2.6$ $2.7$ $2.8$ $2.9$ Answer is $2.9$ My doubt:- But when I am using $log_2n$ for $n = 10$ it is not equal to $2.9$, and $log_210 = 3.3219$ ?
The average successful search time taken by binary search on a sorted array of $10$ items?$2.6$$2.7$$2.8$$2.9$Answer is $2.9$My doubt:- But when I am using $log_2n$ for $...
User Avatar
0 votes
1 answer
46
Binary Stream
We have a run of 0's followed by the run of 1's and we have to find the point where first 1 will be present. We only know the start of the sequence but we have no idea about the end. what should the best case complexity of this problem? Describe your approach.
We have a run of 0's followed by the run of 1's and we have to find the point where first 1 will be present. We only know the start of the sequence but we have no idea ab...
User Avatar
6 votes
3 answers
47
binary search
I/p - array of n element in which untill some postion all are integer and afterward all are star (*) O/p- find the postion of 1st star (*) Hint - if lenear search is possible the go to BS Find time complexity ..?
I/p - array of n element in which untill some postion all are integer and afterward all are star (*) O/p- find the postion of 1st star (*)Hint - if lenear search is possi...
User Avatar
1 votes
1 answer
49
IITd Phd -sample Q
Derive the running time of the binary search algorithm. If I modify binary search to break the interval size into 1/3, 2/3 rather than 1/2, 1/2, then what is the worst case running time?
Derive the running time of the binary search algorithm. If I modify binary search to break the interval size into 1/3, 2/3 rather than 1/2, 1/2, then what is the worst ca...
User Avatar
2 votes
1 answer
50
complexity of different trees
what are the complexities of different trees like BST,AVL,HEAP,B-tree etc for insertion updation deletion for all 3 cases 1)best 2)avg 3)worst
what are the complexities of different trees like BST,AVL,HEAP,B-tree etc for insertion updation deletion for all 3 cases 1)best 2)avg 3)worst
User Avatar
0 votes
1 answer
52
binary search
Stack space used in binary search resursive implementation.
Stack space used in binary search resursive implementation.
User Avatar
2 votes
2 answers
53
Comparisons in a Binary Search
How many comparisons are needed for a binary search in a set of 64 elements?
How many comparisons are needed for a binary search in a set of 64 elements?
User Avatar
3 votes
4 answers
54
ARRAYS
Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time complexity to find the position of the missing element using divide and conquer?
Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time ...
User Avatar
1 votes
1 answer
55
#Algorithm
Given a sorted array of distinct interger A[1...N] , you want to find out whether there is an index "i" for which A[i] =i . if this problem is solved using divide and conquer method,then find time complexity.
Given a sorted array of distinct interger A[1...N] , you want to find out whether there is an index "i" for which A[i] =i . if this problem is solved using divide and con...
User Avatar
1 votes
2 answers
58
Binary Search
What is the worst case complexity for searching for a key in a sorted array using Binary Search??
What is the worst case complexity for searching for a key in a sorted array using Binary Search??
User Avatar
2 votes
2 answers
59
Binary search
If the binary search algorithm determines that the scanned argument is in upper half of the array,which of the following statement will set the appropriate variable to the appropriate value. A) startsub= middlesub-1; B) startsub=middlesub+1; C)stopsub=middlesub-1; D)stopsub=middlesub+1;
If the binary search algorithm determines that the scanned argument is in upper half of the array,which of the following statement will set the appropriate variable to th...
User Avatar
2 votes
1 answer
60
Binary search algorithm employs the strategy of
Binary search algorithm employs the strategy of Divide and Conquer technique Dynamic Programming Branch & Bound technique Greedy Strategy
Binary search algorithm employs the strategy ofDivide and Conquer techniqueDynamic ProgrammingBranch & Bound techniqueGreedy Strategy
User Avatar
Page: