Update Single Element in a Sorted Array.java

varunu28 · web-flow · commit 94b5a78b158c · 2019-12-12T09:21:38.000-08:00
diff --git a/Medium/Single Element in a Sorted Array.java b/Medium/Single Element in a Sorted Array.java
@@ -1,13 +1,25 @@
 class Solution {
-    public int singleNonDuplicate(int[] nums) {
-        boolean evenInd = true;
-        for (int i=0;i<nums.length-1;i++) {
-            if (nums[i] != nums[i+1] && evenInd) {
-                return nums[i];
-            }
-            evenInd = evenInd ? false : true;
-        }
-        
-        return nums[nums.length-1];
+  public int singleNonDuplicate(int[] nums) {
+    if (nums.length == 1) {
+      return nums[0];
     }
+    return binarySearchHelper(nums, 0, nums.length - 1);
+  }
+  
+  private int binarySearchHelper(int[] nums, int start, int end) {
+    if (start > end) {
+      return Integer.MIN_VALUE;
+    }
+    int mid = (start + end) / 2;
+    if (mid == 0 && mid + 1 < nums.length && nums[mid] != nums[mid + 1]) {
+      return nums[mid];
+    }
+    if (mid == nums.length - 1 && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
+      return nums[mid];
+    }
+    if (mid + 1 < nums.length && nums[mid] != nums[mid + 1] && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
+      return nums[mid];
+    }
+    return Math.max(binarySearchHelper(nums, start, mid - 1), binarySearchHelper(nums, mid + 1, end));
+  }
 }
