Recent questions tagged binary-search

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)$
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
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?
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
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?
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?
7
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?
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$ ?
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?
10
How to calculate the time complexity for finding repeated elements in an array of n elements using linear search and binary search?
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?
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.
13
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
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?
15
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
17
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
18
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.
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.
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?
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.
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)
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) ...
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 ..?
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???
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$ ?