回答編集履歴
3
違う、終端条件はそのままでも、再帰の仕方で回避できるんだ
answer
CHANGED
|
@@ -25,19 +25,11 @@
|
|
|
25
25
|
// 幅がゼロなら、見つからなかった
|
|
26
26
|
if (left == right) return null;
|
|
27
27
|
|
|
28
|
-
// 幅が1なら、leftが該当するかどうかで決まる
|
|
29
|
-
// ※swordoneさんご指摘の終端条件
|
|
30
|
-
if (left + 1 == right)
|
|
31
|
-
{
|
|
32
|
-
if (data[left].id == id) return data[left];
|
|
33
|
-
else return null;
|
|
34
|
-
}
|
|
35
|
-
|
|
36
28
|
// 中央
|
|
37
29
|
int pivot = (left + right) / 2;
|
|
38
30
|
|
|
39
31
|
if (data[pivot].id == id) return data[pivot];
|
|
40
|
-
if (data[pivot].id > id) return findMemberById(id, data, pivot, right);
|
|
32
|
+
if (data[pivot].id > id) return findMemberById(id, data, pivot + 1, right);
|
|
41
33
|
return findMemberById(id, data, left, pivot);
|
|
42
34
|
}
|
|
43
35
|
```
|
2
終端条件の追加
answer
CHANGED
|
@@ -25,6 +25,14 @@
|
|
|
25
25
|
// 幅がゼロなら、見つからなかった
|
|
26
26
|
if (left == right) return null;
|
|
27
27
|
|
|
28
|
+
// 幅が1なら、leftが該当するかどうかで決まる
|
|
29
|
+
// ※swordoneさんご指摘の終端条件
|
|
30
|
+
if (left + 1 == right)
|
|
31
|
+
{
|
|
32
|
+
if (data[left].id == id) return data[left];
|
|
33
|
+
else return null;
|
|
34
|
+
}
|
|
35
|
+
|
|
28
36
|
// 中央
|
|
29
37
|
int pivot = (left + right) / 2;
|
|
30
38
|
|
1
findMemberById
answer
CHANGED
|
@@ -1,5 +1,5 @@
|
|
|
1
1
|
```java
|
|
2
|
-
private static Member
|
|
2
|
+
private static Member findMemberById(int id, Member[]data, int left, int right)
|
|
3
3
|
{
|
|
4
4
|
// 略
|
|
5
5
|
}
|
|
@@ -8,11 +8,11 @@
|
|
|
8
8
|
というちょっと引数の余計にあるメソッドを作るところから始めます。
|
|
9
9
|
left, rightとは何か。
|
|
10
10
|
data配列のどこからどこまでを探すかという範囲です。left以上right未満の範囲で調べるということ。
|
|
11
|
-
すると、最初の
|
|
11
|
+
すると、最初のfindMemberByIdの中身はこうなります。
|
|
12
12
|
|
|
13
13
|
```java
|
|
14
14
|
public static Member findMemberById(int id, Member[] data) {
|
|
15
|
-
return
|
|
15
|
+
return findMemberById(id, data, 0, data.length);
|
|
16
16
|
}
|
|
17
17
|
```
|
|
18
18
|
|
|
@@ -20,7 +20,7 @@
|
|
|
20
20
|
二分探索だから、自分自身を利用します。
|
|
21
21
|
|
|
22
22
|
```java
|
|
23
|
-
private static Member
|
|
23
|
+
private static Member findMemberById(int id, Member[]data, int left, int right)
|
|
24
24
|
{
|
|
25
25
|
// 幅がゼロなら、見つからなかった
|
|
26
26
|
if (left == right) return null;
|
|
@@ -29,8 +29,8 @@
|
|
|
29
29
|
int pivot = (left + right) / 2;
|
|
30
30
|
|
|
31
31
|
if (data[pivot].id == id) return data[pivot];
|
|
32
|
-
if (data[pivot].id > id) return
|
|
32
|
+
if (data[pivot].id > id) return findMemberById(id, data, pivot, right);
|
|
33
|
-
return
|
|
33
|
+
return findMemberById(id, data, left, pivot);
|
|
34
34
|
}
|
|
35
35
|
```
|
|
36
36
|
|