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

  <div class='amazlink-detail'>
    渡部 有隆
  <a href='https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957%3FSubscriptionId%3DAKIAJDINZW45GEGLXQQQ%26tag%3Dsleephacker-22%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4839952957

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2">線型探索 - Wikipedia</a>
  </li>
</ul>

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    サンプル問題(AOJ): <a href="https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp">https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp</a>
  </p>
  
  <p>
    [sourcecode language="python" title="" ] n = int(input()) S = list(map(int, input().split())) q = int(input()) T = list(map(int, input().split()))
  </p>
  
  <p>
    def linearSearch(A, n, key): i = 0 A.append(key) # 番兵 while A[i] != key: i += 1 A.pop() return i != n
  </p>
  
  <p>
    count = 0
  </p>
  
  <p>
    for i in range(q): if linearSearch(S, n, T[i]): count += 1
  </p>
  
  <p>
    print(count) [/sourcecode]
  </p>
</div>

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

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2">二分探索 - Wikipedia</a>
  </li>
</ul>

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    サンプル問題(AOJ): <a href="https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp">https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp</a>
  </p>
  
  <p>
    [sourcecode language="python" title="" ] n = int(input()) S = list(map(int, input().split())) q = int(input()) T = list(map(int, input().split()))
  </p>
  
  <p>
    def binary_search(A, key): left = 0 right = n 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="https://python.civic-apps.com/string-find/">文字列検索系メソッド find, index, startswith, endswidth » Python Snippets</a>
          </li>
        </ul>
      </div>
    </div>