search
Log In

Recent questions tagged binary-search

0 votes
1 answer
1
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is $\Theta(\log _{2}n)$ $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$
asked Apr 2 in DS Lakshman Patel RJIT 56 views
2 votes
4 answers
2
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?
asked Jan 16, 2019 in DS sripo 1.1k views
5 votes
4 answers
3
Asha and Lata play a game in which Lata first thinks of a natural number between $1$ and $1000$. Asha must find out that number by asking Lata questions, but Lata can only reply by saying Yes or no . Assume that Lata always tells the truth. What is the least number of ... ask within which she can always find out the number Lata has thought of? $10$ $32$ $100$ $999$ $\text{None of the above}$
asked Dec 18, 2018 in Algorithms Arjun 1.1k views
1 vote
4 answers
4
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 required using binary search and find its time complexity?
asked Dec 15, 2018 in Algorithms Abhishek Kumar 38 413 views
1 vote
1 answer
5
In which of the cases shown below, Binary search can not always be applied for searching (A) Hierarchical data record (B) Internet Domain name conversion (C) Searching a telephone number in directory (D) An array of integers Answer is given to be (D). I thought it must be (B). Please help. I understand (D) is okay when the array is not sorted.But what about other options?
asked Nov 15, 2018 in Programming Ayush Upadhyaya 260 views
3 votes
0 answers
6
Consider a sorted array A of n integer elements, A[0]...A[n − 1]. A search operation is to be performed on this array using .Binary search algorithm. If the element being searched is in fact the last element of the array, what is the difference between the index of element being searched ... This is my answer.But it matches none of the options. Where I went wrong?
asked Nov 15, 2018 in Programming Ayush Upadhyaya 214 views
2 votes
4 answers
7
for binary search in an array of n elements the average number of searches is $\left \lfloor \log_{2}n \right \rfloor$ or $\left \lceil \log_{2}n \right \rceil$ ?
asked Aug 20, 2018 in Algorithms aditi19 608 views
1 vote
1 answer
8
Leading element in an array of n elements is the element which occurs more than n/2 times in the array. a) What is the time complexity to find whether a leading element exists or not in a sorted array of n elements? b)What is the time complexity to find whether a ... are between 0 to n? c)What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?
asked Aug 7, 2018 in Algorithms Sambhrant Maurya 401 views
0 votes
1 answer
9
How to calculate the time complexity for finding repeated elements in an array of n elements using linear search and binary search?
asked Aug 6, 2018 in Algorithms Sambhrant Maurya 241 views
2 votes
6 answers
10
Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that |a-b| = k , k being a positive integer. a) O(logn) b) O(n) c)O(nlogn) d)O(n^2) Which of the option is Correct And Why?
asked Jul 9, 2018 in Algorithms pradeepchaudhary 1.8k views
2 votes
1 answer
11
The average successful search time taken by binary search on a sorted array of 5 CONSECUTIVE integers starting with 1? My Answer is - 2.2 Kindly tell me is it correct or not? NOTE: I have edited the question and changes are shown in highlighted text.
asked Mar 13, 2018 in Algorithms iarnav 586 views
3 votes
2 answers
12
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
asked Mar 8, 2018 in Algorithms rahul sharma 5 790 views
3 votes
0 answers
13
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available in the database. D: ... executed. If Binary Search is used to locate a tuple in a relation using primary key, then what is the range of n?
asked Jan 31, 2018 in Databases Balaji Jegan 328 views
3 votes
1 answer
14
asked Jan 18, 2018 in Algorithms ankit_thawal 257 views
3 votes
2 answers
15
Suppose we have the following sorted list: [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] and array data structure is used. We are using recursive binary search algorithm to search an element 8. Which of the following group of number correctly shown the sequence of comparison used to find element 8? (Assume array index starting with 0). a) 11,5,6,8 b) 12,6,11,8
asked Dec 8, 2017 in Algorithms VS 715 views
4 votes
4 answers
16
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
asked Nov 27, 2017 in DS Parshu gate 1.1k views
7 votes
2 answers
18
Which of the following operations can be performed in O(log n) time or faster on a sorted array A? (n denotes the size of array) 1) Search(A, x) 2) Find-Minimum(A) 3) Delete(A, x) Choose the correct option: A.) 1 & 3 B.) 1 & 2 C.) 2 & 3 D.) All of them I chose option B but the book says option D is right. Please provide an explanation.
asked Nov 22, 2017 in Algorithms Akash Mishra 1.6k views
2 votes
0 answers
19
In this given question I find all answers false because while implementing binary seach or tracing it for an example we need to follow same approach Right? if we are taking ceil for evaluation then it should be considered throughout and if we are taking floor ... it should be traced.Therefore applying both operating individually I find none of the options matching. Correct Me If I am wrong here.
asked Nov 16, 2017 in Algorithms saxena0612 304 views
4 votes
1 answer
20
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 required using binary search is? Their solution : $logn + logn = 2*logn = logn^{2}$. My ... parallel, we return from the search the moment we find the element. So tell me whose solution is correct? Why my solution should be incorrect?
asked Nov 6, 2017 in Algorithms Aghori 419 views
5 votes
3 answers
21
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.
asked Aug 22, 2017 in Algorithms just_bhavana 566 views
9 votes
3 answers
22
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)
asked Aug 16, 2017 in DS Chandramani Adil 678 views
6 votes
5 answers
23
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) ...
asked Aug 10, 2017 in Algorithms air1ankit 970 views
5 votes
4 answers
24
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 ..?
asked Jun 28, 2017 in Algorithms Raushank2 799 views
4 votes
1 answer
25
How is it possible that the time complexity of inorder traversal is O(n), because the time complexity of Inorder Successor in Binary Search Tree is O(log n), So the inorder traversal in BST for printing the numbers take O(n*logn) time for 'n' nodes???
asked Jun 25, 2017 in Algorithms rahulsangwn 476 views
10 votes
2 answers
26
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$ ?
asked Jun 6, 2017 in Algorithms Shubhanshu 2.9k views
6 votes
3 answers
27
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 ..?
asked Mar 9, 2017 in Algorithms air1ankit 708 views
1 vote
1 answer
28
Time complexity to compute the sum of k smallest element in the binary search tree?? can we do it like this- Start doing the inorder traversal of the binary search tree, it will give the elements in increasing order. Start the counter k=0. As we get the elements we increment ... k and sum the elements which we have got. Its time complexity will be O(h+k). Am i right?? plzz plzz explain someone
asked Feb 2, 2017 in Programming sushmita 781 views
4 votes
2 answers
29
Consider an array ‘A’ with 2m elements. The elements in odd position are sorted in non-increasing order that is A[1] >= A[3] >= A[5]......A[2m-1] The elements in even position are sorted in non-decreasing order, that is A[2]<= A[4] <= A[6].....A[2m]. Which of the following method is recommended for finding if a given number is in array?
asked Nov 10, 2016 in Algorithms vaishali jhalani 673 views
0 votes
1 answer
30
Stack space used in binary search resursive implementation.
asked Nov 10, 2016 in Algorithms vaishali jhalani 379 views
...