# O(log n) In-place Recursive Java Solution

• public class Solution {

``````public int singleNonDuplicate(int[] nums) {
if (nums.length == 1) {
return nums[0];
}

if (nums.length == 3) {
if (nums[0] < nums[1] && nums[1] < nums[2]) {
return nums[1];
} else if (nums[0] == nums[1] && nums[1] < nums[2]) {
return nums[2];
} else {
return nums[0];
}
}

// length greater than 3...   ex. 5, 7, 9, ....

int startIndex = 0;
int endIndex = nums.length - 1;
int midIndex = nums.length / 2;

return findSingle(startIndex, endIndex, nums);

}

public static int findSingle(int startIndex, int endIndex, int[] nums) {

int currentLength = endIndex - startIndex + 1;
int midIndex = (startIndex + endIndex) / 2;

if (currentLength == 3) {
if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {
return nums[midIndex];
} else if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {
return nums[midIndex + 1];
} else {
return nums[midIndex - 1];
}
}

// currentLength > 3

if (midIndex % 2 == 0) {    // odd remain

if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {  // turn left
return findSingle(startIndex, midIndex, nums);
} else if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] == nums[midIndex + 1]) {   // turn right
return findSingle(midIndex, endIndex, nums);
} else {
return nums[midIndex];
}

} else {    // even remain

if (nums[midIndex - 1] == nums[midIndex] && nums[midIndex] < nums[midIndex + 1]) {  // turn right
return findSingle(midIndex + 1, endIndex, nums);
} else if (nums[midIndex - 1] < nums[midIndex] && nums[midIndex] == nums[midIndex + 1]) {   // turn left
return findSingle(startIndex, midIndex - 1, nums);
} else {
return nums[midIndex];      // impossible ?
}

}

}
``````

}

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