線形探索法（リニアサーチ）と２分探索法（バイナリサーチ）

前回こんな記事を書いたのですが、

その流れで、基本情報技術者試験のアルゴリズムに出てくるデータ探索アルゴリズム

についてRubyとGo言語で書いてみようと思います。

（ただブログネタが思いつかなかっただけです。ハイ〜。）

線形探索法（リニアサーチ）

ただ先頭から目的の値があるか調べていく。

ということでintの配列（Goの場合はスライス）から目的の値のインデックスを調べるコードを書いてみます。

Ruby

# リニアサーチ（線形探索法）
def linear_search(ary, value)
  ary.each_with_index do |v, i|
    return i if v == value
  end

  return nil
end

ary = [1, 15, 2, 3, 8, 7, 10]
puts linear_search(ary, 7) # => 5
puts linear_search(ary, 4) # => nil

以上！！

Go言語

package main

import "fmt"

func main() {
	s := []int{1, 15, 2, 3, 8, 7, 10}
	if index, found := linearSearch(s, 7); found {
		fmt.Printf("Found!! index = %d\n", index) // => 5
	} else {
		fmt.Println("Not Found")
	}

	if index, found := linearSearch(s, 4); found {
		fmt.Printf("Found!! index = %d\n", index)
	} else {
		fmt.Println("Not Found") // => Not Found
	}
}

func linearSearch(s []int, value int) (int, bool) {
	for i := range s {
		if s[i] == value {
			return i, true
		}
	}

	return 0, false
}

以上！！Go言語の方は返り値を２つにして、見つかったかどうかを表すboolを返すようにしてみました。

２分探索法（バイナリサーチ）

探索対象の配列が既にソートされている場合に使える方法で、配列を２つに分けながら探索していく。

具体的な探索方法は バイナリサーチとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典 に詳しく書いてあります。

Ruby

# バイナリサーチ（２分探索法）
def binary_search(ary, value)
  left, right = 0, ary.length - 1

  result = nil
  while right >= left
    middle = (left + right) / 2
    puts "left: #{left}, middle: #{middle}, right: #{right}"
    if ary[middle] == value
      result = middle
      break
    end

    if ary[middle] > value
      right = middle - 1
    else
      left = middle + 1
    end
  end

  return result
end

ary = [1, 4, 5, 7, 10, 13, 21, 29, 33, 40, 57]
puts binary_search(ary, 40) # => 9
puts binary_search(ary, 9) # => nil (not found)

Go言語

package main

import "fmt"

func main() {
	s := []int{1, 4, 5, 7, 10, 13, 21, 29, 33, 40, 57}
	if index, found := binarySearch(s, 40); found {
		fmt.Printf("Found!! index = %d\n", index) // => 9
	} else {
		fmt.Println("Not Found") // => Not Found
	}

	if index, found := binarySearch(s, 9); found {
		fmt.Printf("Found!! index = %d\n", index)
	} else {
		fmt.Println("Not Found") // => Not Found
	}
}

func binarySearch(s []int, value int) (int, bool) {
	left, right := 0, len(s)-1

	var index int
	var found bool
	for right >= left {
		middle := (left + right) / 2
		if s[middle] == value {
			index = middle
			found = true
			break
		}

		if s[middle] > value {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}

	return index, found
}

アルゴリズムを学びたい人におすすめ

Udemyの「現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門」　がおすすめです。

わかりやすいスライドを使って、どういったアルゴリズムなのか解説してくれます。