アルゴリズム 線形探索（Linear Search）
線形探索は配列やリスト内の要素を先頭から順にサーチしていき、目的の要素と比較を行います。
先頭から順に比較していくので、最小の場合は1回で済みますが最悪の場合はn回実行されることになり、計算量は最大計算量を使用するので、線形探索の場合の計算量は「O(n)」になります。
Javaで線形探索
public class LinearSearch { public static void main(String[] args) { int[] dataes = {10, 8, 9, 3, 2, 1, 4, 6, 5, 0}; System.out.println("result index = " + search(dataes, 2)); } public static int search(int[] dataes, int valueToFind) { for (int i = 0; i < dataes.length; i++) { if (dataes[i] == valueToFind) { return i; } } return -1; } }
Pythonで線形探索
def search(dataes, valueToFind): for i, data in enumerate(dataes): if data == valueToFind: return i; return -1 if __name__ == '__main__': dataes = [10, 8, 9, 3, 2, 1, 4, 6, 5, 0] print 'result index = %s' % search(dataes, 2)
関連書籍
