# Accepted java solution using binary search

• ``````public void nextPermutation(int[] num) {
if (num.length < 2) {
return;
}
int tail = num.length - 1;
//traverse from the last element, find the first element that is smaller than num[tail]
while (tail > 0 && num[tail - 1] >= num[tail]) {
tail--;
}
//this means num is in an descending order, just reverse it.
if (tail == 0) {
reverse(num, 0, num.length - 1);
return;
}
else {
//the index of the first element that is smaller than its next (traverse from the end of num)
int k = tail - 1;
//find the index of the least element that is larger than num[k], search from num[k-1] to the end
int nextLarger = firstLarger(num, tail, num.length-1,num[k]);
//swap these two elements
swap(num, k, nextLarger);
//reverse the remaining sub-array
reverse(num, tail, num.length - 1);
return;
}
}
//reverse the sub-array, num[i] to num[j]
public void reverse(int[] num, int i, int j) {
for (int k = i; k <= (j + i) / 2; k++) {
swap(num, k, j + i - k);
}
}
//swap num[i] and num[j]
public void swap(int[] num, int i, int j) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}

//find the index of the least element from num[start] to num[end], which is larger than k (binary seaerch)
public int firstLarger(int[] num, int start, int end, int k) {
if (end-start+1 == 1) {
return start;
}
int i = start, j = end;
while (i < j) {
int mid = (i + j) / 2;
if (num[mid] == k) {
while (num[mid] == k) {
mid--;
}
return mid;
} else if (num[mid] > k) {
if (num[mid + 1] <= k) {
return mid;
} else {
i = mid + 1;
}
} else {
j = mid - 1;
}
}
return i;

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.