Algorithm | 線形探索(順次検索, Linear search)
線形探索アルゴリズム(順次検索, Linear search algorithm)
探したい値をリストの先頭から末尾まで順番に探していくアルゴリズムである。
- メリット: 検索方法の中で最も単純で実装しやすく、ソートされていないリストでも使える。
- デメリット: 検索するリストの長さが長いと非効率である。
package com.devkuma.algorithum.programming.search.linear;
public class LinearSearch {
void search(int[] nums, int target) {
int index = -1;
for(int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
index = i + 1;
break;
}
}
if (index > 0) {
System.out.println(target + "은 " + index + "번째 있습니다.");
} else {
System.out.println(target + "은 없습니다.");
}
}
public static void main(String[] args) {
LinearSearch search = new LinearSearch();
search.search(new int[]{1, 5, 3, 2, 8, 9}, 8);
search.search(new int[]{1, 5, 3, 2, 8, 9}, 4);
}
}
実行結果:
8은 5번째 있습니다.
4은 없습니다.
線形探索アルゴリズムで最小値を求める
以下のコードは、すべての要素についてminValueより小さい値が見つかるたびにminValueを更新して最小値を求める。
(最大値も同じアルゴリズムである)
package com.devkuma.algorithum.programming.search.linear;
public class MinLinearSearch {
void searchMinimum(int[] nums) {
int minValue = Integer.MAX_VALUE; // 最大値
for(int i = 0; i < nums.length; i++) {
if (nums[i] < minValue) {
minValue = nums[i];
}
}
System.out.println("최소값은 " + minValue + "입니다.");
}
public static void main(String[] args) {
MinLinearSearch search = new MinLinearSearch();
search.searchMinimum(new int[]{1, 5, 3, 2, 8, 9});
search.searchMinimum(new int[]{2, 7, 8, 6, 5, 4});
}
}
実行結果:
최소값은 1입니다.
최소값은 2입니다.
線形探索アルゴリズムで問題を解く
線形探索アルゴリズムを使って問題を解いてみる。
問題
N個の整数a(0), a(1), ..., a(N-1)とb(0), b(1), ..., b(N-1)があるとき、この2つの数列からそれぞれ1つずつ数a(i), b(j) [i = 0, 1, ..., N-1, j = 0, 1, ..., N-1]を選び、その和が整数R以上となる範囲での最小値を求めよ。
解決方法
package com.devkuma.algorithum.programming.linearsearch;
public class LinearSearchQuiz1 {
void minSum(int[] aNums, int[] bNums, int r) {
int minSum = Integer.MAX_VALUE; // 最大値
for(int i = 0; i < aNums.length; i++) {
for(int j = 0; j < bNums.length; j++) {
int sum = aNums[i] + bNums[j];
if (sum >= r && minSum > sum) {
minSum = sum;
}
}
}
System.out.println("최소값은 " + minSum + "입니다.");
}
public static void main(String[] args) {
LinearSearchQuiz1 search = new LinearSearchQuiz1();
int[] aNums = new int[]{9, 5, 3, 7, 8, 9};
int[] bNums = new int[]{3, 9, 5, 8, 3, 5};
int r = 7;
search.minSum(aNums, bNums, 7);
}
}
実行結果:
최소값은 8입니다.
上記の例の計算量はO(N^2)になる。