ここでは、二分探索(Binary Search)について、 「プログラミングコンテストチャレンジブック(第2版)」(通称:蟻本)の p26〜28 を例に、python3 で実装する方法を紹介します。

 まずは p26 からの「3重ループ + 二分探索」による方法です。

# 入力
n = 3
m = 4
k = [1, 3, 5]

def binary_search(x):
    # xの存在し得る範囲はk[l], k[l+1], ..., k[r-1]
    l, r = 0, n
    
    #範囲に何も含まれなくなるまで繰り返す
    while (r - l >= 1):
        i = int((l+r)/2)
        if k[i] == x:
            return True #見つかった
        elif k[i] < x:
            l = i + 1
        else:
            r = i
    #見つからなかった
    return False
    
def solve():
    #二分探索を行うためにソート
    k.sort()
    
    f = False
    
    for a in range(n):
        for b in range(n):
            for c in range(n):
                #最も内側のループの代わりに二分探索
                if binary_search(m - k[a] - k[b] - k[c]):
                    f = True
                    
    if f:
        print('Yes')
    else:
        print('No')
        

#実行
solve()
        

続いて、p27 からの 「2重ループ + 二分探索」による方法です。

# 入力
n = 3
m = 10
k = [1, 3, 5]

# 2つで作れる数を格納する配列
kk = [0] * (n * n)

def binary_search(x):
    # xの存在し得る範囲はkk[l], kk[l+1], ..., kk[r-1]
    l, r = 0, n * n
    
    #範囲に何も含まれなくなるまで繰り返す
    while (r - l >= 1):
        i = int((l+r)/2)
        if kk[i] == x:
            return True #見つかった
        elif kk[i] < x:
            l = i + 1
        else:
            r = i
    #見つからなかった
    return False
    
def solve():
    # k[c] + k[d]の取り得る範囲を列挙
    for c in range(n):
        for d in range(n):
            kk[c * n + d] = k[c] + k[d]      
    #二分探索を行うためにソート
    kk.sort()

    f = False
    for a in range(n):
        for b in range(n):
            #内側のループの代わりに二分探索
            if binary_search(m - k[a] - k[b]):
                f = True
                    
    if f:
        print('Yes')
    else:
        print('No')
        

#実行
solve()

 ちなみに、二分探索の部分については、python3 の 「bisect」というライブラリを使用することで、以下のように書くこともできます。

import bisect # <- インポートが必要です

# 入力
n = 3
m = 18
k = [1, 3, 5]

# 2つで作れる数を格納する配列
kk = [0] * (n * n)
    
def solve():
    # k[c] + k[d]の取り得る範囲を列挙
    for c in range(n):
        for d in range(n):
            kk[c * n + d] = k[c] + k[d]      
    #二分探索を行うためにソート
    kk.sort()

    f = False
    for a in range(n):
        for b in range(n):
            # m - k[a] - k[b] の値を kk 内に挿入するとしたら、
            #どの位置に入るかを二分探索で pos として取得
            pos = bisect.bisect_left(kk, m - k[a] - k[b])
            # pos が kk 内にあり(=最も右側ではない)、
            # kk[pos] が探しているそのものである場合は、すなわち見つかった
            if pos < (n * n) and kk[pos] == (m - k[a] - k[b]):
                f = True
                    
    if f:
        print('Yes')
    else:
        print('No')
        

#実行
solve()
       


お役に立てれば、うれしいです。