search
Log In

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)$
asked Feb 18 in Algorithms Arjun 1.1k views
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)$
asked Apr 2, 2020 in DS Lakshman Patel RJIT 779 views
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?
asked Jan 16, 2019 in DS sripo 2.8k views
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}$
asked Dec 18, 2018 in Algorithms Arjun 2k views
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?
asked Dec 15, 2018 in Algorithms Abhishek Kumar 38 778 views
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?
asked Nov 15, 2018 in Programming Ayush Upadhyaya 382 views
3 votes
0 answers
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?
asked Nov 15, 2018 in Programming Ayush Upadhyaya 321 views
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$ ?
asked Aug 20, 2018 in Algorithms aditi19 1k views
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?
asked Aug 7, 2018 in Algorithms Sambhrant Maurya 645 views
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?
asked Aug 6, 2018 in Algorithms Sambhrant Maurya 334 views
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?
asked Jul 9, 2018 in Algorithms pradeepchaudhary 4.2k views
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.
asked Mar 13, 2018 in Algorithms iarnav 926 views
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
asked Mar 8, 2018 in Algorithms rahul sharma 5 1.2k views
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?
asked Jan 31, 2018 in Databases Balaji Jegan 476 views
3 votes
1 answer
15
asked Jan 18, 2018 in Algorithms ankit_thawal 322 views
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
asked Dec 8, 2017 in Algorithms VS 1.6k views
4 votes
4 answers
17
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 2k views
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.
asked Nov 22, 2017 in Algorithms Akash Mishra 3k views
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.
asked Nov 16, 2017 in Algorithms saxena0612 427 views
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?
asked Nov 6, 2017 in Algorithms Aghori 528 views
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.
asked Aug 22, 2017 in Algorithms just_bhavana 649 views
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)
asked Aug 16, 2017 in DS Chandramani Adil 833 views
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) ...
asked Aug 10, 2017 in Algorithms air1ankit 1.3k views
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 ..?
asked Jun 28, 2017 in Algorithms Raushank2 1.2k views
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???
asked Jun 25, 2017 in Algorithms rahulsangwn 569 views
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$ ?
asked Jun 6, 2017 in Algorithms Shubhanshu 5.7k views
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 ..?
asked Mar 9, 2017 in Algorithms air1ankit 864 views
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
asked Feb 2, 2017 in Programming sushmita 911 views
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[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 1.1k views
...