Next Permutation of an Integer or string

Problem: Given an integer(or string), get the integer that is just bigger than it (lexicographical order).

Example:  given 507632, we need find 520367; given 123, we need find 1023.  

Solution: Basically, we need something like next_permutation in STL, but we can implement by our own.

1. Start from the end, we try to find the longest non-increasing sequence. Then the integer (or string) is divided into halves. For the tail part, we can't find one that is bigger than it. Then we need to think of the front part.
2. We swap the last element a of the front part with the element b in the tail part that is the smallest one but bigger than a. swap a and b. The tail part is still a non-increasing sequence. We just reverse it and append it to the front part. The reverse is neat!
3. for the case where the integer (or string) is already the biggest one, we need to add zero.

The code is as follow (not consider the case that needs adding zero):

char* next_perm(char* s, int len)
{

    int i = len-1;

    while(i>=1 && s[i-1] >= s[i])
          i--;

    if(i==0)  return 0;

    int lo = i;
    int hi = len - 1;
    
    //binary search
    int c = s[i-1];
    
    while(lo < hi)
    {
      int mid = lo + (hi - lo)/2;
      if(s[mid] <= c)
           hi = mid-1;
      else if(s[mid] > c)
      {     
         if(mid+1 <= hi && s[mid+1] <=c)
         {   
           lo = mid;
           break;
         }
         lo = mid+1;
      }
    
    }
    
    s[i-1] = s[lo];
    s[lo] = c;

    //reverse
    lo = i;
    hi = len - 1;

    while(lo<hi)
    {
       char t = s[lo];
       s[lo] = s[hi];
       s[hi] = t;
       lo++;
       hi--;
    }

    return s;
}