Skip to content

Commit 35b4331

Browse files
fishercoder1534fishercoder1534
committed
add a solution for 33
1 parent cb00e1c commit 35b4331

File tree

2 files changed

+187
-15
lines changed

2 files changed

+187
-15
lines changed

‎src/main/java/com/fishercoder/solutions/_33.java

Lines changed: 57 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@
33
public class _33 {
44

55
public static class Solution1 {
6-
76
public int search(int[] nums, int target) {
87
if (nums == null || nums.length == 0) {
98
return -1;
@@ -50,29 +49,74 @@ public int search(int[] nums, int target) {
5049
if (nums == null || nums.length == 0) {
5150
return -1;
5251
}
53-
int lo = 0;
54-
int hi = nums.length - 1;
55-
while (lo < hi) {
56-
int mid = (lo + hi) / 2;
52+
int left = 0;
53+
int right = nums.length - 1;
54+
while (left < right) {
55+
int mid = (left + right) / 2;
5756
if (nums[mid] == target) {
5857
return mid;
5958
}
6059

61-
if (nums[lo] <= nums[mid]) {
62-
if (target >= nums[lo] && target < nums[mid]) {
63-
hi = mid - 1;
60+
if (nums[left] <= nums[mid]) {
61+
if (target >= nums[left] && target < nums[mid]) {
62+
right = mid - 1;
6463
} else {
65-
lo = mid + 1;
64+
left = mid + 1;
6665
}
6766
} else {
68-
if (target > nums[mid] && target <= nums[hi]) {
69-
lo = mid + 1;
67+
if (target > nums[mid] && target <= nums[right]) {
68+
left = mid + 1;
69+
} else {
70+
right = mid - 1;
71+
}
72+
}
73+
}
74+
return nums[left] == target ? left : -1;
75+
}
76+
}
77+
78+
public static class Solution3 {
79+
/**
80+
* My completely original solution on 10/23/2021, although spaghetti code.
81+
*/
82+
public int search(int[] nums, int target) {
83+
int left = 0;
84+
int right = nums.length - 1;
85+
while (left < right) {
86+
if (nums[left] == target) {
87+
return left;
88+
} else if (nums[right] == target) {
89+
return right;
90+
}
91+
int mid = left + (right - left) / 2;
92+
if (left == mid || right == mid) {
93+
break;
94+
}
95+
if (nums[mid] == target) {
96+
return mid;
97+
} else if (nums[mid] > target && nums[right] > target && nums[left] > target) {
98+
if (nums[right] < nums[mid]) {
99+
left = mid + 1;
100+
} else {
101+
right = mid - 1;
102+
}
103+
} else if (nums[mid] > target && nums[right] < target) {
104+
right = mid - 1;
105+
} else if (nums[mid] < target && nums[right] > target) {
106+
left = mid + 1;
107+
} else if (nums[mid] < target && nums[right] < target && nums[left] < target) {
108+
if (nums[mid] < nums[left] && nums[mid] < nums[right]) {
109+
right = mid - 1;
70110
} else {
71-
hi = mid - 1;
111+
left = mid + 1;
72112
}
113+
} else if (nums[mid] > target && nums[left] < target) {
114+
right = mid;
115+
} else if (nums[mid] < target && nums[right] < target && nums[left] > target) {
116+
right = mid - 1;
73117
}
74118
}
75-
return nums[lo] == target ? lo : -1;
119+
return (right >= 0 && nums[right] == target) ? right : (nums[left] == target) ? left : -1;
76120
}
77121
}
78122
}

‎src/test/java/com/fishercoder/_33Test.java

Lines changed: 130 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,18 +9,146 @@
99
public class _33Test {
1010
private static _33.Solution1 solution1;
1111
private static _33.Solution2 solution2;
12+
private static _33.Solution3 solution3;
1213
private static int[] nums;
14+
private static int expected;
15+
private static int target;
1316

1417
@BeforeClass
1518
public static void setup() {
1619
solution1 = new _33.Solution1();
1720
solution2 = new _33.Solution2();
21+
solution3 = new _33.Solution3();
1822
}
1923

2024
@Test
2125
public void test1() {
2226
nums = new int[]{4, 5, 6, 7, 0, 1, 2};
23-
assertEquals(3, solution1.search(nums, 7));
24-
assertEquals(3, solution2.search(nums, 7));
27+
expected = 3;
28+
target = 7;
29+
assertEquals(expected, solution1.search(nums, target));
30+
assertEquals(expected, solution2.search(nums, target));
31+
assertEquals(expected, solution3.search(nums, target));
2532
}
33+
34+
@Test
35+
public void test2() {
36+
nums = new int[]{4, 5, 6, 7, 0, 1, 2};
37+
expected = 4;
38+
target = 0;
39+
assertEquals(expected, solution1.search(nums, target));
40+
assertEquals(expected, solution2.search(nums, target));
41+
assertEquals(expected, solution3.search(nums, target));
42+
}
43+
44+
@Test
45+
public void test3() {
46+
nums = new int[]{4, 5, 6, 7, 0, 1, 2};
47+
expected = 1;
48+
target = 5;
49+
assertEquals(expected, solution1.search(nums, target));
50+
assertEquals(expected, solution2.search(nums, target));
51+
assertEquals(expected, solution3.search(nums, target));
52+
}
53+
54+
@Test
55+
public void test4() {
56+
nums = new int[]{4, 5, 6, 7, 0, 1, 2};
57+
expected = -1;
58+
target = 3;
59+
assertEquals(expected, solution1.search(nums, target));
60+
assertEquals(expected, solution2.search(nums, target));
61+
assertEquals(expected, solution3.search(nums, target));
62+
}
63+
64+
@Test
65+
public void test5() {
66+
nums = new int[]{1};
67+
expected = -1;
68+
target = 0;
69+
assertEquals(expected, solution1.search(nums, target));
70+
assertEquals(expected, solution2.search(nums, target));
71+
assertEquals(expected, solution3.search(nums, target));
72+
}
73+
74+
@Test
75+
public void test6() {
76+
nums = new int[]{1, 3, 5};
77+
expected = -1;
78+
target = 4;
79+
assertEquals(expected, solution1.search(nums, target));
80+
assertEquals(expected, solution2.search(nums, target));
81+
assertEquals(expected, solution3.search(nums, target));
82+
}
83+
84+
@Test
85+
public void test7() {
86+
nums = new int[]{1, 3, 5};
87+
expected = -1;
88+
target = 6;
89+
assertEquals(expected, solution1.search(nums, target));
90+
assertEquals(expected, solution2.search(nums, target));
91+
assertEquals(expected, solution3.search(nums, target));
92+
}
93+
94+
@Test
95+
public void test8() {
96+
nums = new int[]{1, 3, 5};
97+
expected = -1;
98+
target = 2;
99+
assertEquals(expected, solution1.search(nums, target));
100+
assertEquals(expected, solution2.search(nums, target));
101+
assertEquals(expected, solution3.search(nums, target));
102+
}
103+
104+
@Test
105+
public void test9() {
106+
nums = new int[]{5, 1, 3};
107+
expected = -1;
108+
target = 4;
109+
assertEquals(expected, solution1.search(nums, target));
110+
assertEquals(expected, solution2.search(nums, target));
111+
assertEquals(expected, solution3.search(nums, target));
112+
}
113+
114+
@Test
115+
public void test10() {
116+
nums = new int[]{1, 2, 3, 4, 5, 6};
117+
expected = 3;
118+
target = 4;
119+
assertEquals(expected, solution1.search(nums, target));
120+
assertEquals(expected, solution2.search(nums, target));
121+
assertEquals(expected, solution3.search(nums, target));
122+
}
123+
124+
@Test
125+
public void test11() {
126+
nums = new int[]{5, 1, 2, 3, 4};
127+
expected = 1;
128+
target = 1;
129+
assertEquals(expected, solution1.search(nums, target));
130+
assertEquals(expected, solution2.search(nums, target));
131+
assertEquals(expected, solution3.search(nums, target));
132+
}
133+
134+
@Test
135+
public void test12() {
136+
nums = new int[]{8, 9, 2, 3, 4};
137+
expected = 1;
138+
target = 9;
139+
assertEquals(expected, solution1.search(nums, target));
140+
assertEquals(expected, solution2.search(nums, target));
141+
assertEquals(expected, solution3.search(nums, target));
142+
}
143+
144+
@Test
145+
public void test13() {
146+
nums = new int[]{4, 5, 6, 7, 8, 1, 2, 3};
147+
expected = 4;
148+
target = 8;
149+
assertEquals(expected, solution1.search(nums, target));
150+
assertEquals(expected, solution2.search(nums, target));
151+
assertEquals(expected, solution3.search(nums, target));
152+
}
153+
26154
}

0 commit comments

Comments
 (0)