@sys Thanks a lot. That's the most helpful topic there !
T
thms_la
@thms_la
53
Reputation
3
Posts
103
Profile views
0
Followers
0
Following
Posts made by thms_la

RE: Visualization  No Code

RE: Java Binary Search O(log(n)) Shorter Than Others
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 :)

Java Binary Search, short (7l), O(log(n)) w/ explanations
All credits go to @Penghuan who thought of using the pairs wisely.
This method seems to be a bit simpler to understand, since it doesn't start with the left half and stays a little bit closer to the conventional solutions.
public static int singleNonDuplicate(int[] nums) { int start = 0, end = nums.length  1; while (start < end) { // We want the first element of the middle pair, // which should be at an even index if the left part is sorted. // Example: // Index: 0 1 2 3 4 5 6 // Array: 1 1 3 3 4 8 8 // ^ int mid = (start + end) / 2; if (mid % 2 == 1) mid; // We didn't find a pair. The single element must be on the left. // (pipes mean start & end) // Example: 0 1 1 3 3 6 6 // ^ ^ // Next: 0 1 13 3 6 6 if (nums[mid] != nums[mid + 1]) end = mid; // We found a pair. The single element must be on the right. // Example: 1 1 3 3 5 6 6 // ^ ^ // Next: 1 1 3 35 6 6 else start = mid + 2; } // 'start' should always be at the beginning of a pair. // When 'start > end', start must be the single element. return nums[start]; }