题目

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

原题链接

题解

这道题本质上是一个搜索类的题目，最常用的无非就是线性搜索，如果题目给的数组是已经排好序的，用二分搜索即可

线性搜索

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        for(char c:letters){
            if(c>target) return c;
        }
        return letters[0];
    }
};

低配版二分搜索

这里所说的低配版，是自己手写的一个二分搜索。

用了二分搜索后程序所需的时间和空间显著降低

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        if(target >= letters[letters.size()-1]) return letters[0];
        return findBinary(letters,target,0,letters.size()-2);
    }

    char findBinary(vector<char>& letters,char target,int l, int r){
        int mid = (l+r)/2;
        if(mid == 0 && letters[mid] > target)return letters[0]; 
        if(letters[mid + 1] > target && letters[mid]<=target) return letters[mid + 1];
        if(letters[mid] > target) return findBinary(letters,target,l,mid);
        if(letters[mid + 1]<= target) return findBinary(letters,target,mid + 1,r);
        return letters[0];
    }
};

c++ 自带的二分搜索

这次让我学到东西了，原来c++还有自带的二分搜索。

已知letters是vector类型的，

letters.back() 取得是该vector的最后一个元素
upper_bound(letters.begin(), letter.end(),target ), 前两个位置传的是迭代器，后面一个是目标，这个返回的是该大于target的迭代器，
low_bound()传参和upper_bound一样，主要区别在于该函数放回的是不大于target的迭代器

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        return target >= letters.back() ? (letters[0]) : *upper_bound(letters.begin(),letters.end(),target); 
    }
};