# 要素数Nの配列Aの区間[0, N)からkeyの位置を探す
binarySearch(A, N, key):
    left ← 0
    right ← N  
    while left < right:
        mid ← (left + right)/2
        if  A[mid] = key:
            return mid
        else if A[mid] < key:
            left ← mid + 1
        else
            right ← mid

    return NIL # 存在しない