# Single Element in a Sorted Array

Ventured into LeetCode and randomly selected the Single Element in a Sorted Array challenge. The requirements are very straight forward. Make sure you pay attention to the following Note: Your solution should run in O(log n) time and O(1) space.

Thought about the linear O(n) brute force approach. I did not bother playing with it given that it was not going to work. Doodle for a few minutes with the numbers and their indices in the array. The solution smelled like a binary search which requires a sorted array of elements.

The following screen capture is from the Eclipse IDE using sample data provided by the challenge and some that I made up:

```1,1,2,3,3,4,4,8,8
3,3,7,7,10,11,11
1,1,9
1,8,8
3,3,9,9,10,13,13
1,1,8,10,10
1,1,2,2,8,10,10
-1

main <<< str ==>1,1,2,3,3,4,4,8,8<==
main <<< nums:  1  1  2  3  3  4  4  8  8
0  1  2  3  4  5  6  7  8
2
main <<< str ==>3,3,7,7,10,11,11<==
main <<< nums:  3  3  7  7 10 11 11
0  1  2  3  4  5  6
10
main <<< str ==>1,1,9<==
main <<< nums:  1  1  9
0  1  2
9
main <<< str ==>1,8,8<==
main <<< nums:  1  8  8
0  1  2
1
main <<< str ==>3,3,9,9,10,13,13<==
main <<< nums:  3  3  9  9 10 13 13
0  1  2  3  4  5  6
10
main <<< str ==>1,1,8,10,10<==
main <<< nums:  1  1  8 10 10
0  1  2  3  4
8
main <<< str ==>1,1,2,2,8,10,10<==
main <<< nums:  1  1  2  2  8 10 10
0  1  2  3  4  5  6
8
main <<< str ==>-1<==
```

The sequence is terminated by a line with a -1. I display the values in the nums array separated by a space. The following line is the index in the nums array. The number left justified is the missing number.

My solution and test code written in Java 8 follows:

```import java.util.Scanner;

public class Solution {

/**
* 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.
*/
static int singleNonDuplicate(int[] nums) {
int lo 	= 0;
int hi 	= nums.length - 1;
int mid	= 0;

// **** ****

while (lo <= hi) {
mid = lo + (hi - lo) / 2;

// **** ****

if (lo == hi) {
return nums[mid];
}

// **** ****

if ((nums[mid - 1] != nums[mid]) &&
(nums[mid] != nums[mid + 1])) {
return nums[mid];
}

// **** ****

if ((mid % 2) == 0) {		// even
if (nums[mid] == nums[mid - 1]) {
hi = mid + 1;		// go up
} else {
lo = mid - 1;		// go down
}
} else {					// odd
if (nums[mid] == nums[mid - 1]) {
lo = mid + 1;		// go up
} else {
hi = mid - 1;		// go down
}
}
}

// **** ****

return -1;
}

/**
* Test code.
*/
public static void main(String[] args) {

// ***** open scanner ****

Scanner sc = new Scanner(System.in);

// **** loop until told to exit ****

Boolean done = false;
while (!done) {

// **** ****

String str = sc.nextLine();
System.out.println("main <<< str ==>" + str + "<==");

// **** check if we are done ****

if (str.equals("-1")) {
done = true;
continue;
}

// **** build array of integers ****

String ints[] = str.split(",");
int[] nums = new int[ints.length];
System.out.print("main <<< nums: ");
for (int i = 0; i < ints.length; i++) {
nums[i] = Integer.parseInt(ints[i]);
System.out.printf("%2d ", nums[i]);
}
System.out.println();
System.out.print("               ");
for (int i = 0; i < ints.length; i++) {
System.out.printf("%2d ", i);
}
System.out.println();

// **** call method ****

System.out.println(singleNonDuplicate(nums));
}

// **** close scanner ****

sc.close();

}

}
```

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

Enjoy;

John

john.canessa@gmail.com