You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears only once. Design an efficient algorithm for finding which value appears only once. Here are some example inputs to the problem:

1 1 2 2 3 4 4 5 5 6 6 7 7 8 8

10 10 17 17 18 18 19 19 21 21 23

1 3 3 5 5 7 7 8 8 9 9 10 10

Notice that the problem can be solved through a linear search in O(n). However, the problem demands a better solution, i.e., an algorithm that runs in O(log n).

(a) Design an algorithm for non-duplicate finding problem. Write the pseudocode and derive the complexity.

(b)Using loop invariants, argue for the correctness of the problem.