# Recent questions tagged searching 1 vote
1
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$’s followed by a sequence of $1$’s. The problem is to find the smallest index $i$ such that $A[i]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is $2$ $4$ $3$ $5$
2
Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?
3
Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, ... iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (lg\ n)$.
4
Consider the linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in ‚-notation? Justify your answers.
5
Consider the searching problem: Input: A sequence of $n$ numbers $A = \langle a_1, a_2,\dots a_n \rangle$ and a value $v$ Output: An index $i$ such that $v=A[i]$ or the special value NIL if $v$ does not appear in $A$. Write ... sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
6
.Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]=i. Ans should be O(log n) right by doing binary search ??
7
A sequential search operation is performed on an array $A$ for the key value of $'x'$ (ignore quotes). Consider the following piece of assembly language code that uses back patching to perform the sequential search. i=0; P: if (i<A.length) goto ____; Q: goto ____; R: if (x==A[i] ... What should be the correct values in the blanks provided ordered from top to bottom? R T U P R U T P P U T R P T U R
8
Which is faster and by how much, a linear search of only 1000 elements on a 5-GHz computer or a binary search of 1 million elements on a 1-GHz computer. Assume that the execution of each instruction on the 5-GHz computer is five times faster than on the 1-GHz computer and that each iteration of the linear search algorithm is twice as fast as each iteration of the binary search algorithm.
9
This question is not related to GATE, but certainly would help you to grill your mind to come up with a better approach.. Feel free to comment if you think, this is not a right forum for this question. I have 10 LDAP systems which contain users and ... said format. The format cannot be changed as there is dependency with other downstream systems. Is there a better approach to achieve the same ?
10
Which of the following search method takes less memory ? Depth-first search Breadth-first search Linear search None of the above
11
12
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.
13
can someone provide me the detailed description for this answer?
14
An $A^{*}$ algorithm is a heuristic search technique which Is like a depth-first search where most promising child is selected for expansion Generates all successor nodes and computes an estimate of distance (cost) from start node to a goal node through each of ... all path lengths (costs) from start node to all generated nodes and chooses shortest path for further expansion. None of the above
15
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if( ... $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
16
Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sorted. i, j, k : integer; a : array [1....N] of T; x : T; Program 1 : i := 1; j := N ... correct Only Program $2$ is correct Only Program $1$ and $2$ are correct. Both Program $2$ and $3$ are correct All the three programs are wrong
17
Suppose you are given an array $A$ with $2n$ numbers. The numbers in odd positions are sorted in ascending order, that is, $A \leq A \leq \ldots \leq A[2n - 1]$. The numbers in even positions are sorted in descending order, that ... binary search on the entire array. Perform separate binary searches on the odd positions and the even positions. Search sequentially from the end of the array.
18
Consider the following program that attempts to locate an element $x$ in an array $a[ ]$ using binary search. Assume $N > 1$. The program is erroneous. Under what conditions does the program fail? var i,j,k: integer; x: integer; a: array; [1..N] of integer; begin i:= 1; j:= n; repeat k: ... x) or (i >= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n-1}{2}$ $\frac{n+1}{2}$ None of the above
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n-1$ $2n$ $\frac{n}{2}$
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] ... $x > 2$ $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $2 < x < 20$ and $x$ is even