# Recent questions tagged binary-search 1 vote
3 answers
1
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
0 votes
1 answer
2
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)$
3 votes
4 answers
3
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?
7 votes
5 answers
4
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}$
1 vote
4 answers
5
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?
2 votes
1 answer
6
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?
3 votes
0 answers
7
Consider a sorted array A of n integer elements, A...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?
2 votes
4 answers
8
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$ ?
3 votes
1 answer
9
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?
0 votes
1 answer
10
How to calculate the time complexity for finding repeated elements in an array of n elements using linear search and binary search?
3 votes
7 answers
11
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?
2 votes
1 answer
12
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.
3 votes
2 answers
13
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
3 votes
0 answers
14
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?
3 votes
1 answer
15
3 votes
2 answers
16
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
4 votes
4 answers
17
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
3 votes
1 answer
18
7 votes
2 answers
19
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.
2 votes
0 answers
20
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.
4 votes
1 answer
21
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?
6 votes
3 answers
22
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.
9 votes
3 answers
23
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)
6 votes
5 answers
24
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) ...
5 votes
4 answers
25
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 ..?
4 votes
1 answer
26
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???
11 votes
2 answers
27
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$ ?
6 votes
3 answers
28
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 ..?
1 vote
1 answer
29
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
4 votes
2 answers
30
Consider an array ‘A’ with 2m elements. The elements in odd position are sorted in non-increasing order that is A >= A >= A......A[2m-1] The elements in even position are sorted in non-decreasing order, that is A<= A <= A.....A[2m]. Which of the following method is recommended for finding if a given number is in array?