refactor 35 to log(n) solution

fishercoder1534 · fishercoder1534 · commit 06f3863f46d9 · 2021-09-12T10:46:26.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_35.java b/src/main/java/com/fishercoder/solutions/_35.java
@@ -4,13 +4,19 @@ public class _35 {
 
     public static class Solution1 {
         public int searchInsert(int[] nums, int target) {
-            int len = nums.length;
-            for (int i = 0; i < len; i++) {
-                if (target <= nums[i]) {
-                    return i;
+            int left = 0;
+            int right = nums.length - 1;
+            while (left < right) {
+                int mid = left + (right - left) / 2;
+                if (nums[mid] == target) {
+                    return mid;
+                } else if (nums[mid] < target) {
+                    left = mid + 1;
+                } else {
+                    right = mid - 1;
                 }
             }
-            return len;
+            return nums[left] >= target ? left : left + 1;
         }
     }
 
diff --git a/src/test/java/com/fishercoder/_35Test.java b/src/test/java/com/fishercoder/_35Test.java
@@ -20,4 +20,10 @@ public void test1() {
         nums = new int[]{1, 3, 5, 6};
         assertEquals(2, solution1.searchInsert(nums, 5));
     }
+
+    @Test
+    public void test2() {
+        nums = new int[]{1};
+        assertEquals(0, solution1.searchInsert(nums, 1));
+    }
 }

Original file line number	Diff line number	Diff line change
`@@ -4,13 +4,19 @@ public class _35 {`
`4`	`4`
`5`	`5`	`public static class Solution1 {`
`6`	`6`	`public int searchInsert(int[] nums, int target) {`
`7`		`- int len = nums.length;`
`8`		`- for (int i = 0; i < len; i++) {`
`9`		`- if (target <= nums[i]) {`
`10`		`- return i;`
	`7`	`+ int left = 0;`
	`8`	`+ int right = nums.length - 1;`
	`9`	`+ while (left < right) {`
	`10`	`+ int mid = left + (right - left) / 2;`
	`11`	`+ if (nums[mid] == target) {`
	`12`	`+ return mid;`
	`13`	`+ } else if (nums[mid] < target) {`
	`14`	`+ left = mid + 1;`
	`15`	`+ } else {`
	`16`	`+ right = mid - 1;`
`11`	`17`	`}`
`12`	`18`	`}`
`13`		`- return len;`
	`19`	`+ return nums[left] >= target ? left : left + 1;`
`14`	`20`	`}`
`15`	`21`	`}`
`16`	`22`
Original file line number	Diff line number	Diff line change
`@@ -20,4 +20,10 @@ public void test1() {`
`20`	`20`	`nums = new int[]{1, 3, 5, 6};`
`21`	`21`	`assertEquals(2, solution1.searchInsert(nums, 5));`
`22`	`22`	`}`
	`23`	`+`
	`24`	`+ @Test`
	`25`	`+ public void test2() {`
	`26`	`+ nums = new int[]{1};`
	`27`	`+ assertEquals(0, solution1.searchInsert(nums, 1));`
	`28`	`+ }`
`23`	`29`	`}`