05 Dec 2015, 06:55

リスト探索(線形探索・二分探索) – Python

こんにちは。今日は、AOJ の問題に取り組むことで、探索の勉強をしてみました!

線形探索

[sourcecode language=”text” title=”” ]
リストや配列に入ったデータに対する検索を行うにあたって、
先頭から順に比較を行い、それが見つかれば終了する.
[/sourcecode]

ALDS1_4_A:

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def linearSearch(A, n, key):<br /> i = 0<br /> A.append(key) # 番兵<br /> while A[i] != key:<br /> i += 1<br /> A.pop()<br /> return i != n
  </p>

  <p>
    count = 0
  </p>

  <p>
    for i in range(q):<br /> if linearSearch(S, n, T[i]):<br /> count += 1
  </p>

  <p>
    print(count)<br /> [/sourcecode]
  </p>
</div>

二分探索

ソート済み配列に対する探索アルゴリズムの一つ

[sourcecode language=”text” title=”” ]
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、
中央の値を見て、検索したい値との大小関係を用いて、
検索したい値が中央の値の右にあるか、左にあるかを判断して、
片側には存在しないことを確かめながら検索していく
[/sourcecode]

ALDS1_4_B:

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def binary_search(A, key):<br /> left = 0<br /> right = n<br /> while left < right: mid = int((left + right)/2) if A[mid] == key: return True elif key < A[mid]: right = mid else: left = mid + 1 return False cnt = 0 for i in T: if binary_search(S, i): cnt += 1 print(cnt) [/sourcecode] </div> </div> </div> 

    <div id="outline-container-orgheadline5" class="outline-2">
      <h2 id="orgheadline5">
        Pythonの(文字列)探索ライブラリ
      </h2>

      <div class="outline-text-2" id="text-orgheadline5">
        <p>
          find, indexがある.
        </p>

        <ul class="org-ul">
          <li>
            <a href="http://python.civic-apps.com/string-find/">文字列検索系メソッド find, index, startswith, endswidth » Python Snippets</a>
          </li>
        </ul>
      </div>
    </div>