Question

Subject: Algorithm

4. Give pseudocode for an algorithm that will solve the following problem. Given an array A[1..n) that contains every number between 1 and n +1 in order, except that one of the numbers is missing. Find the miss sorted ing mber. Your algorithm should run in time (log n). (Hint: Modify Binary search). A pseudocode means an algorithm with if statements and loops, etc. Don't just write a paragraph. Also, if your algorithm is unclear, please explain what it does.

need this urgent please thank you.

Answer 1

1. let x = 1, y = n

2. middle_pt = (x+y) / 2

3. run step 4. to 6. while ((y - x) > 1)

4. middle_pt = (x + y) / 2;

5. if ((A[x] - x) is not equal to (A[middle_pt] - middle_pt))

then y = middle_pt

6. else if ((A[y] - y) is not equal to (A[middle_pt] - middle_pt))

then x = middle_pt

7. return (A[middle_pt] + 1) {Missing Element}

here the indexing is starting from 1

The concept behind this solution is that the elements appearing before the missing element will have A[i] – i = 0 and those appearing after the missing element will have A[i] – i = 1.