Recent questions tagged binary-search

Which of the following cannot be a sequence of keys compared during a binary search for some target key?$500,200,450,180$ $500,450,200,180$ $180,500,200,450$ $180,200,500...

Suppose Binary Search is used in Insertion Sort to locate where the $i$th element should be inserted among the first $i-1$ elements.What is the worst-case running time of...

A sorted table contains $2000$ distinct elements in increasing order. A key is searched using binary search, and it is guaranteed that the key exists in the table.What is...

Let A be a sorted array containing $1000$ distinct integers. You perform a recursive binary search on $\text{A}$ to find an element $\text{y}$. Suppose each comparison ch...

For which of the following inputs does binary search take time $O(\log n)$ in the worst case?An array of $n$ integers in any orderA linked list of $n$ integers in any ord...

​​​​​Let $F(n)$ denote the maximum number of comparisons made while searching for an entry in a sorted array of size $n$ using binary search.Which ONE of the following op...

Bob writes down a number between 1 and 1,000. Mary must identify that number by asking "yes/no" questions of Bob. Mary knows that Bob always tells the truth. If Mary uses...

Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). Ho...

Let $A$ be a sorted array containing $n$ distinct integers, such that, for all $1 \leq i<j \leq n$, we have $A[i]<A[j]$. Note that the integers stored in the array $A$ ar...

You are given two sorted arrays $X[\;]$ and $Y[\;]$ of positive integers. The array sizes are not given. Accessing any index beyond the last element of the arrays returns...

The recurrence relation for binary search algorithm is :$\text{T(n) = 2T (n/2) + O (1)}$$\text{T(n) = 2T (n/2) + O (n)}$$\text{T(n) = T (n/2) + O (1)}$$\text{T(n) = T (n/...

The program written for binary search, calculates the midpoint of the span as $\text{mid : =(Low+High)/2}$. The program works well if the number of elements in the list i...

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 ...

Given a sorted array of distinct integers A[1,2,3,..,n], the tightest upper bound to check the existence of any index i for which A[i]= i is equal to O($n^{a}log^{b}n)$. ...

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 onl...

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 ...

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 t...

The average number of comparisons made by binary search for an unsuccessful search in array A

https://gateoverflow.in/18752/tifr2010-b-29IN THIS QUESTION WHY WE CANT NOT APPLY SINGLE BINARY SEARCH ON ENTIRE ARRAY ???BECAUSE LET WE HAVE ARRAY 1 14 3 12 5 10 7 8 9 ...

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$ ?

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)