You are given as input an array A[1..n], with n entries, all 0 or 1. Further- more you know that the array consists of a series of 0's followed by a series of 1's, but you don't know how many of each there are (could be no 0's or no 1's). Your goal is to nd the rst 1 in the array, if it exists, and for this purpose you are given a set of blue chips and a set of red chips. Each time you check a value in the array A, and it turns out to be 0, you must pay 1 red chip. If the value turns out to be 1, you have to pay 1 blue chip. If you can't pay (because you ran out) you lose. In each of the parts of this question, we list the number of red and blue chips you have. You must give an algorithm which will return the index of the rst (lowest index) 1, which works given your resources, i.e. without losing { or prove that no algorithm could work. For each case write pseudocode and explain your answers. Assume n is large.

You have 2 red chips and 2 sqrt(n )blue chips.

You have 2 red chips and sqrt(n) blue chips.

Programming language does not matter. Python is preferred, though.