タグ: VB.net 配列 検索

配列から条件に一致する値を検索する

example(VB.net)

Sub Main()
   Dim n() As Integer = {0, 1, 2, 3, 2, 5, 6, 7, 2, 9}

   '最初に条件に一致する値を取得する
   Dim FirstValue As Integer = Array.Find(n, AddressOf MyFind)
   '条件に一致する値をすべて取得する
   Dim FindAllvalue() As Integer = Array.FindAll(n, AddressOf MyFind)
   '最後に条件に一致する値を取得する
   Dim LastValue As Integer = Array.FindLast(n, AddressOf MyFind)

   'Linqを使用すると簡単!!
   Dim ret As Integer() = (From C As Integer In n Where C = 2).ToArray()
End Sub

Function MyFind(ByVal val As Integer) As Boolean
   Dim BaseValue As Integer = 2
   Return val = BaseValue
End Function

比較する処理をMyFind関数内で行っています。

この関数内で比較する処理を変更することで、より複雑な比較条件が可能となります。


バイナリーサーチ

バイナリーサーチとは、配列がソート済みの場合に使用できる検索方法で、検索対象データを半分ずつに絞って行く検索方法です。 以下のサンプルはどちらもarrayが検索対象の配列、valueが検索する値です。

バイナリーサーチ(VB.net)

Function Two_DivSearch(ByVal array() As Integer, ByVal value As Integer) As Integer
  Dim s As Integer = 0
  Dim e As Integer = UBound(array)
  While s <= e
    Dim mid As Integer = (s + e) / 2
    If value = array(mid) Then Return mid
    If value < array(mid) Then
      e = mid - 1
    Else
      s = mid + 1
    End If
  End While
  Return -1
End Function

三分岐検索(VB.net)

Function Three_DivSearch(ByVal array() As Integer, ByVal value As Integer) As Integer
  Dim s As Integer = 0
  Dim e As Integer = UBound(Array)
  While s <= e
    Dim ukey As Integer = e - (e - s) / 3
    Dim lkey As Integer = s + (e - s) / 3
    Select Case value
      Case array(ukey) : Return ukey
      Case array(lkey) : Return lkey
      Case Is < array(lkey) : e = lkey - 1
      Case Is > array(ukey) : s = ukey + 1
      Case Else
        s = lkey + 1
        e = ukey - 1
    End Select
  End While
  Return -1
End Function

Googleの入社試験にもあった「9個のボールの中から一個だけ質量の違うのを探すのに、天秤は最少で何回使用するか??」の模範解答を参考に3分岐検索も作ってみました。

検索対象を三分割した上をukey、下をlkeyとします。そのどちらかが示すの配列の要素と、検索値が同じなら該当の添え字を返して終了です。

次に、検索値が配列の要素"lkey"未満なら検索の範囲をlkey未満に、検索値が配列の要素"ukey"以上なら検索の範囲をukey以上に絞ります。

そして、そのどちらでもない場合は検索の範囲をlkeyからukeyの間に絞り込みます。

使用方法

Sub Main()
  Dim array() As Integer = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18}
  Do Until True = False
    Console.Write("input-< ")
    Dim ret As Integer = CInt(Console.ReadLine())
 
    Console.WriteLine("2 ->" & vbTab & Two_DivSearch(array, ret))
    Console.WriteLine("3 ->" & vbTab & Three_DivSearch(array, ret))
  Loop
End Sub

検索方法

実行時間(ミリ秒)

検索方法

Linq使用時

実行時間(ミリ秒)

161890

検索方法

バイナリサーチ

実行時間(ミリ秒)

48

検索方法

三分岐検索

実行時間(ミリ秒)

25