今日のトピックは「線形探索と二分探索の違いと使い方」です。どちらもデータ構造において要素を検索するためのアルゴリズムですが、それぞれに適した状況があります。
線形探索と二分探索の特徴を理解し、適切に使い分けることで、データ検索の効率を大幅に向上させることができます。
目次
基本概念の説明
線形探索（Linear Search）
線形探索（Linear Search）は、リストや配列などのデータ構造内を先頭から順に探索し、目的の要素を見つけるアルゴリズムです。この方法は、データが未ソートでも利用できますが、大量のデータを扱う場合には非効率的になることがあります。
二分探索（Binary Search）
二分探索（Binary Search）は、データがソートされている場合に使用できる効率的な探索アルゴリズムです。リストを半分に分割し、目的の要素がどちらの半分にあるかを判断しながら探索を繰り返します。この方法により、検索の時間を大幅に短縮できます。
各言語での線形探索と二分探索の実装例
Python:
# 線形探索
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 二分探索
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
C#:
using System;
class Program
{
static int LinearSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
return i;
}
return -1;
}
static int BinarySearch(int[] arr, int target)
{
int left = 0, right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
static void Main()
{
int[] numbers = { 1, 3, 5, 7, 9, 11 };
Console.WriteLine(LinearSearch(numbers, 7)); // 出力: 3
Console.WriteLine(BinarySearch(numbers, 7)); // 出力: 3
}
}
C++:
#include <iostream>
#include <vector>
#include <algorithm>
int linear_search(const std::vector<int>& arr, int target) {
for (size_t i = 0; i < arr.size(); ++i) {
if (arr[i] == target)
return i;
}
return -1;
}
int binary_search(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
std::vector<int> numbers = {1, 3, 5, 7, 9, 11};
std::cout << linear_search(numbers, 7) << std::endl; // 出力: 3
std::cout << binary_search(numbers, 7) << std::endl; // 出力: 3
return 0;
}
Java:
public class Main {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {1, 3, 5, 7, 9, 11};
System.out.println(linearSearch(numbers, 7)); // 出力: 3
System.out.println(binarySearch(numbers, 7)); // 出力: 3
}
}
JavaScript:
// 線形探索
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
// 二分探索
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
const numbers = [1, 3, 5, 7, 9, 11];
console.log(linearSearch(numbers, 7)); // 出力: 3
console.log(binarySearch(numbers, 7)); // 出力: 3
各言語の解説
| 言語 | 線形探索の実装方法 | 二分探索の実装方法 |
|---|---|---|
| Python | ループでarr[i]を順番にチェック | ループでarr[mid]をチェック |
| C# | ループでarr[i]を順番にチェック | ループでarr[mid]をチェック |
| C++ | ループでarr[i]を順番にチェック | ループでarr[mid]をチェック |
| Java | ループでarr[i]を順番にチェック | ループでarr[mid]をチェック |
| JavaScript | ループでarr[i]を順番にチェック | ループでarr[mid]をチェック |
まとめ
今日は線形探索と二分探索の違いと使い方について学びました。線形探索はデータが未ソートでも使えますが、効率が悪いことがあります。一方、二分探索はデータがソートされている場合に非常に効率的
コメント