teratail
回答率
85.47%
質問するログイン新規登録
トップJavaに関する質問2分探索と線形探索

編集履歴

回答編集履歴

3

違う、終端条件はそのままでも、再帰の仕方で回避できるんだ

2016/11/07 16:41

投稿

yuba
yuba

スコア5568

test CHANGED
@@ -52,22 +52,6 @@
52
52
 
53
53
 
54
54
 
55
- // 幅が1なら、leftが該当するかどうかで決まる
56
-
57
- // ※swordoneさんご指摘の終端条件
58
-
59
- if (left + 1 == right)
60
-
61
- {
62
-
63
- if (data[left].id == id) return data[left];
64
-
65
- else return null;
66
-
67
- }
68
-
69
-
70
-
71
55
  // 中央
72
56
 
73
57
  int pivot = (left + right) / 2;
@@ -76,7 +60,7 @@
76
60
 
77
61
  if (data[pivot].id == id) return data[pivot];
78
62
 
79
- if (data[pivot].id > id) return findMemberById(id, data, pivot, right);
63
+ if (data[pivot].id > id) return findMemberById(id, data, pivot + 1, right);
80
64
 
81
65
  return findMemberById(id, data, left, pivot);
82
66
 

2

終端条件の追加

2016/11/07 16:41

投稿

yuba
yuba

スコア5568

test CHANGED
@@ -52,6 +52,22 @@
52
52
 
53
53
 
54
54
 
55
+ // 幅が1なら、leftが該当するかどうかで決まる
56
+
57
+ // ※swordoneさんご指摘の終端条件
58
+
59
+ if (left + 1 == right)
60
+
61
+ {
62
+
63
+ if (data[left].id == id) return data[left];
64
+
65
+ else return null;
66
+
67
+ }
68
+
69
+
70
+
55
71
  // 中央
56
72
 
57
73
  int pivot = (left + right) / 2;

1

findMemberById

2016/11/07 16:39

投稿

yuba
yuba

スコア5568

test CHANGED
@@ -1,6 +1,6 @@
1
1
  ```java
2
2
 
3
- private static Member findByMemberById(int id, Member[]data, int left, int right)
3
+ private static Member findMemberById(int id, Member[]data, int left, int right)
4
4
 
5
5
  {
6
6
 
@@ -18,7 +18,7 @@
18
18
 
19
19
  data配列のどこからどこまでを探すかという範囲です。left以上right未満の範囲で調べるということ。
20
20
 
21
- すると、最初のfindByMemberByIdの中身はこうなります。
21
+ すると、最初のfindMemberByIdの中身はこうなります。
22
22
 
23
23
 
24
24
 
@@ -26,7 +26,7 @@
26
26
 
27
27
  public static Member findMemberById(int id, Member[] data) {
28
28
 
29
- return findByMemberById(id, data, 0, data.length);
29
+ return findMemberById(id, data, 0, data.length);
30
30
 
31
31
  }
32
32
 
@@ -42,7 +42,7 @@
42
42
 
43
43
  ```java
44
44
 
45
- private static Member findByMemberById(int id, Member[]data, int left, int right)
45
+ private static Member findMemberById(int id, Member[]data, int left, int right)
46
46
 
47
47
  {
48
48
 
@@ -60,9 +60,9 @@
60
60
 
61
61
  if (data[pivot].id == id) return data[pivot];
62
62
 
63
- if (data[pivot].id > id) return findByMemberById(id, data, pivot, right);
63
+ if (data[pivot].id > id) return findMemberById(id, data, pivot, right);
64
64
 
65
- return findByMemberById(id, data, left, pivot);
65
+ return findMemberById(id, data, left, pivot);
66
66
 
67
67
  }
68
68