PLEASE GUIDE WITHIN 48 HOURS PLEASE! :) THANK YOU VERY MUCH IN ADVANCE!

You are a police officer trying to crack a case. You want to check whether an important file is in the evidence room. Files have IDs that are positive integers and the evidence room contains n files in sorted order of their IDs. Unfortunately, you do not have direct access to the evidence room; the only one who has access is Randy, who is cormupt and wants to make things hard for you. In the following we assume that r is the file ID you are looking for. . You know that the evidence room is organized as a sorted list of n elements. If Randy was not corrupt you would probably do binary search by asking him to give you the median file of the list. Unfortunately, you can only give Randy two indices I, u and he returns to you a file with index chosen uniformly at random from the range,u. That is you can call RANDY (I, u) = (i, ai), where i is a uniformly random integer chosen from l, . . . , u inclusive and a, is the ID of the coresponding file. You solve the problem by doing something similar to binary search. You start by calling RANDY (1,m). Let's assume that Randy returns (i,ai). You compare r to a If ai you found the file you were looking for If r ai you call RANDY1,n You continue recursively until you have either found the file or conclude that the file is not present in the evidence Ologn) files in expectation before it terminates You are a police officer trying to crack a case. You want to check whether an important file is in the evidence room. Files have IDs that are positive integers and the evidence room contains n files in sorted order of their IDs. Unfortunately, you do not have direct access to the evidence room; the only one who has access is Randy, who is cormupt and wants to make things hard for you. In the following we assume that r is the file ID you are looking for. . You know that the evidence room is organized as a sorted list of n elements. If Randy was not corrupt you would probably do binary search by asking him to give you the median file of the list. Unfortunately, you can only give Randy two indices I, u and he returns to you a file with index chosen uniformly at random from the range,u. That is you can call RANDY (I, u) = (i, ai), where i is a uniformly random integer chosen from l, . . . , u inclusive and a, is the ID of the coresponding file. You solve the problem by doing something similar to binary search. You start by calling RANDY (1,m). Let's assume that Randy returns (i,ai). You compare r to a If ai you found the file you were looking for If r ai you call RANDY1,n You continue recursively until you have either found the file or conclude that the file is not present in the evidence Ologn) files in expectation before it terminates