Algorithm for searching


Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:

  1. Choose an i at random from 1..n
  2. 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?

  1. n
  2. n−1
  3. 2n
  4. n2
shivani @shivani1234
15 Oct 2017 07:57 pm
n , consider in worst case , it might be the case last random index is the correct index.
Gaurav Mohla @gauravmohla
15 Oct 2017 08:13 pm

I am tending towards n but how can we be sure that the same random index is not again picked?

shivani @shivani1234
15 Oct 2017 10:52 pm

you can use some random number generator in which there is no repetition of numbers more appropriately some formulae to calculate random index,
like i= (i-2)%5678 something like this.

Gaurav Mohla @gauravmohla
16 Oct 2017 12:27 am

its not given in the question. how can I be sure. This could go in an infinite loop

shivani @shivani1234
16 Oct 2017 10:57 am

random number is calculated by a predefined formula .