teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

二分探索時の中央インデックスの算出訂正と線形探索について追加

2016/11/07 16:53

投稿

swordone
swordone

スコア20675

answer CHANGED
@@ -4,8 +4,8 @@
4
4
  // 左右が逆になってしまったら、見つからなかった
5
5
  if (left > right) return null;
6
6
 
7
- // 中央
7
+ // 中央 こう書かないと、(あまりないだろうが)オーバーフローが発生してしまうとのこと。
8
- int pivot = (left + right) / 2;
8
+ int pivot = left + (right - left) / 2;
9
9
 
10
10
  if (data[pivot].id == id) return data[pivot];
11
11
  // 範囲中央のidが探索対象idより小さい場合、小さい側(左半分)に可能性はない
@@ -13,4 +13,7 @@
13
13
  // 範囲中央のidが探索対象idより大きい場合、大きい側(右半分)に可能性はない
14
14
  else return findMemberById(id, data, left, pivot - 1);
15
15
  }
16
- ```
16
+ ```
17
+
18
+ 線形探索に関しては、配列の先頭から順番に名前を探せばいいです。
19
+ ってかこれくらいググればすぐ出て来る。