Searching: Given a string and a key, find the smallest letter that is greater than the key

Problem Statement:

Given a string and a key, find the smallest letter that is greater than the key

Example:

Input: str = ["a", "b", "e"] key = "c"

Output: e 

Solution Explanation:

we can use binary search to solve the problem.

We look at the middle of the list, if the middle element is greater than the key, then we look at the left side.

If middle is not bigger, we look at the right side.

Time Complexity: O(logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <deque>

using namespace std;


char solution(vector<char>& letters, char target) 
{
    int low = 0;
    int high = letters.size()-1;

    char maxChar =char(1+'z');

    char ans = maxChar;
    
    while(low <= high)
    {
        int mid = low+(high-low)/2;

        if(target < letters[mid])
        {
            ans = min(ans,letters[mid]);
            high = mid-1;
        }
        else
        {
            low = mid+1;
        }
    }

    if(ans == maxChar)
    {
        return letters[0];
    }
    return ans;
}

int main()
{
    vector<char> letters{ 'a', 'b', 'd' };
    char key = 'c';

    cout << solution(letters, key) << endl;
    return 0;
}

Output

d