Question

Discuss a situation in which you would use a recursive binary search. What is the stopping condition in the recursive binary search?

Please use own words not a google searched article.

Answer 1

Consider a situation where A game is build which has a leaderboard. The leaderboard will have the scores in a sorted order since after completion of each game the scores will be given from highest to lowest(sorted in descending order). After the calculation of the scores based on the scores the rank will be given to each player, to search for the rank based on the score we have to use binary search because it will be the most efficient algorithm since the data is in sorted order, it will compute in O(logn) time complexity. To search in the leaderboard there will be slight modification since the data is sorted in descending order. i.e if the current score is less than the middle of the leaderboard then it will search in the right direction, if the current score is greater than the middle of the leaderboard then it will search for the left side of the leaderboard. The stopping rule is if the middle score of the leader board is equal to the current score the algorithm will return the index + 1 which is the rank of the particular user.
pesudocode will be like this

BinarySearch(left, right, leaderboard)
{
   middle = (left + right)/2;
   if(leaderboard[middle] == currentscore)
   {
       return index + 1;
   }
   elseif(leaderboard[middle] < currentscore)
   {
       return BinarySearch(left, middle, leaderboard);
   }
   elseif(leaderboard[middle] > currentscore)
   {
       return BinarySearch(middle + 1, right, leaderboard);
   }
}

If you have any doubts please comment and please don't dislike.