Alarmed at the performance of students in the first midterm

Alarmed at the performance of students in the first midterm, Professor Dumbledore decided to allow limited consultation in the second midterm. He first arranged students in an arbitrary order and then stipulated that every student is only allowed to discuss answers with her two neighbors (one neighbor for the students at the two ends... tough luck). Not surprisingly, students who discussed among themselves ended up obtaining very similar scores: in fact, the scores of any pair of adjacent students turned out to differ by at most 1. Formally, if X = x_1, x_2, ..., x_n is an array of students\' scores in the order in which they were arranged, then |x_i - x_i + 1| lessthanorequalto 1 for 1 lessthanorequalto i lessthanorequalto n - 1. Also, suppose x_1 lessthanorequalto x_n. Given a particular number x_1 lessthanorequalto b lessthanorequalto x_n, can you help the professor find at least one student who got a score of b in O(log n) time? Note that there may be multiple students with a score of b but you only need to find one. You can assume that all the scores are integers and b is an integer as well.

Solution

When | x_i - x_i+1 | <=1 that means numbers are arranged in increasing /decreasing order and the difference between them is less than equal to 1
1. 5 5 6 6 7 7 8 9 10 ....etc
2. 10 9 8 7 6 5 5 4 4 3 2 1 0 -1 etc

Now x₁ <= b <= x_n    i.e b lies between one of any number or equal to them

We can apply Binary search to find a number b

void FindStudent(int marks[], int b) {
take low = 0 and high = n
while(low<=high){

int mid = ( low +high) /2;

if (marks[mid]==b)
    return mid;
if(marks[mid]< b)
    low = mid +1;
else
high = mid -1 ;
}

}

1. Find mid and Search in the middle ..if we got the student with b marks then return mid
2. Then if middle marks is more than b then student with mark b is on the left , Make high as mid-1.
3. Otherwise if middle marks is less than b then student with mark b is on the right , Make low as mid+1.

In this way we are dividing the array by 2 everytime. Hence the Time complexity is O(log n).