アルゴリズム
問題を解くための効率的手順を定式化した形で表現したものである。
ソート
※Q(n2)はデータ数がn倍になれば、計算量はn2倍になること。
サーチ
遂次探索法
２分探索法
数列の先頭から順に目的のデータを探索する
あらかじめソートされた数列に対し、
二つのグループに分け、目的のデータがどちらのグループに
属するかを調べるのを繰り返す
O((n + 1) / 2)
Q(log2n)
２分探索法
public int binarySearch(int a[], int r) {
int start = 0;
int middle = 0;
int end = a.length - 1;
while (start <= end) {
middle = (start + end) / 2;
if (r == a[middle]) {
return middle;
} else if (r < a[middle]) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return -1;
}
