# Java Binary Search O(log(n)) Shorter Than Others

• My solution using binary search. lo and hi are not regular index, but the pair index here. Basically you want to find the first even-index number not followed by the same number.

``````public class Solution {
public int singleNonDuplicate(int[] nums) {
// binary search
int n=nums.length, lo=0, hi=n/2;
while (lo < hi) {
int m = (lo + hi) / 2;
if (nums[2*m]!=nums[2*m+1]) hi = m;
else lo = m+1;
}
return nums[2*lo];
}
}
``````

• very elegant solution. thank you

• This post is deleted!

• @rishavrastogi Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

• So GREAT and concise!

• how do you get that? That's really wise!

• Great execution. I did something similar in JavaScript:

``````var singleNonDuplicate = function(nums) {
let low = 0;
let high = nums.length - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
let delta = mid % 2 ? -1 : 1;
if (nums[mid] === nums[mid + delta]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return nums[low] === nums[low - 1] ? nums[low + 1] : nums[low];
};
``````

• If you have a hard time understanding this solution's algorithm, I made another version based on his idea. Feel free to have a look at it :)

• Thanks for sharing. I have a question, in a binary search problem, how do you know to determine the updating of `hi` and `lo`?

For example, in regular binary search, we usually do something like `hi = m - 1`. But in your algorithm, the right updating for `hi` would be `hi = m`. I wonder if there is any rule of thumb that I can apply when designing a binary search variation problem or is it that you just have to try it out by cases? Thank you.

... to find the first even-index number not followed by the same number.

Your code is very concise, but not that easy to understand.

Why not do it with a Standard Binary Search. >3<

``````public class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length-1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int even = (mid % 2 == 0)? nums[mid] : nums[mid-1];
int followingOdd = (mid % 2 == 0)? nums[mid+1] : nums[mid];
if (even == followingOdd) {
lo = mid + 1;
} else {
hi = (mid / 2) * 2;
}
}
return nums[lo];
}
}
``````

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