AとBがこれよりも優れた実行時の複雑さを達成するためにソートされているという事実を利用した新しいアルゴリズムを書くにはどうすればよいですか？

Question

Algorithm bar(A,n,B,m) 
    Input: arrays of integers, A of length n and B of length m 
    Output: true or false 

for i := 0 to n-1 
    for j := 0 to m-1 
     if A[i] == B[j] 
      return true 
     endif 
    endfor 
endfor 

return false 

Answer 1

どちらB又はAに進め、同時に終了するように最初から両方のアレイを横断することができ、素子が小さくによってその上に（アレイがascendinglyソートされると仮定）：

def bar(A, n, B, m): 
    x = 0 
    y = 0 

    while x < n and y < m: 
     if A[x] < B[y]: 
      x++ 
     elif A[x] > B[y]: 
      y++ 
     else: 
      return True 

    return False 

ワーストケース実行時間になりますO(n + m) - 一致するペアを見つけることなく、両方の配列を1回トラバースします。