( a & b )

Q2: A SKIP array S[0.1 1) is an array of n integers, where n > 1, in which S[0] = 0 and S[n - 1] = n. i is a SKIP index in a SKIP array S if n >i> 0 and S[i] > S[i - 1] +1. (a) Explain why every SKIP array has at least one SKIP index. (b) Give the pseudocode of a O(log n)-time algorithm that takes as input a SKIP array and returns one of its SKIP indices. Example: The SKIP array {0,2,3,0,4,6} has 3 SKIP indices: 1,4, and 5