前回こんな記事を書いたのですが、
-
-
【独学出身現役エンジニアが解説】基本情報技術者試験の内容は意味あり!!
自己紹介 フリーランスエンジニアをしているヨノと申します。 独学でプログラミングを学び、ソシャゲ・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の「現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門」 がおすすめです。
わかりやすいスライドを使って、どういったアルゴリズムなのか解説してくれます。