プログラミング学習

線形探索法(リニアサーチ)と2分探索法(バイナリサーチ)

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

【独学出身現役エンジニアが解説】基本情報技術者試験の内容は意味あり!!

自己紹介 フリーランスエンジニアをしているヨノと申します。 独学でプログラミングを学び、ソシャゲ・SaaS開発などを経て、2018年からフリーランスエンジニアとして活動しています。 主にバックエンド中 ...

続きを見る

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

  • 「線形探索法(リニアサーチ)」
  • 「2分探索法(バイナリサーチ)」

について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言語の方は返り値を2つにして、見つかったかどうかを表すboolを返すようにしてみました。

2分探索法(バイナリサーチ)

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

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

Ruby

# バイナリサーチ(2分探索法)
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の「現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門」 がおすすめです。

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

現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門

-プログラミング学習

© 2021 フリエン生活 Powered by AFFINGER5