IP02-09 実践プログラム②　探索アルゴリズム　二分探索

関数(メソッド)名	種類	説明
generate_array(size, low, high)	ユーザー定義	重複無しで、要素数size個のランダムなデータを作成する。データの値はlow～highまでの範囲で作成され、昇順に整列する。
random.sample	ライブラリ	重複の無い乱数を作成する。プログラムの先頭に「import random」を記述することで利用することができる。
int	組み込み	値を整数に変換する。
input	組み込み	キーボードからデータを入力する。入力された値はすべて文字列として入力される。
len	組み込み	配列の要素数を返す。例えば配列dataの要素数が10の場合、len(data)は10を表す。

参考

メソッド：メソッドとは、Pythonで用意された部品(クラス)の機能のこと。呼び出すことで機能を利用することができる。

種類：関数にはプログラマが独自で作成したユーザ関数とあらかじめPythonのシステムが用意した組み込み関数やよく利用するものをまとめたライブラリなどがあります。

今回作成する二分探索のプログラムは（ａ）、（ｂ）の2箇所空欄があります。

二分探索プログラム

import random

# 配列をランダムに生成する関数
def generate_array(size=10, low=1, high=100):
    """
    ランダムな整数の昇順配列を生成する（二分探索なのでソート必須）
    size : 要素数
    low  : 最小値
    high : 最大値
    """
    arr = random.sample(range(low, high+1), size)  # 重複なし
    arr.sort()  # 二分探索には昇順に整列が必要
    return arr

# ===== メイン処理 =====

# ランダムに配列を作成
data = generate_array(20, 1, 100)
print("探索対象データ:", data)

# 探す値を入力
target = int(input("探す値を入力してください: "))

# フラグと探索範囲の変数
found_flag = False
low = 0
high = len(data) - 1 #配列の要素数(len(data)) - 1　で配列の最終添字を求める

# フラグを条件に使った二分探索（繰り返し処理）
while found_flag != True and low <= high: 
    middle = (low + high) // 2    # 中央の添字middleの計算
    if data[middle] == target:
        found_flag = True
    elif data[middle] < target:
        （ａ）
    else:
        （ｂ）

# 結果表示
if found_flag == True: 
    print("見つかりました。")
else:
    print("見つかりませんでした。")

（ａ）、（ｂ）は、二分探索の範囲を変更する処理です。

範囲を変更するってことは、lowとhighに値を入れ直すってことだった。

そうそう、middleを使って求めるんだったよね。

そうですが、わからなくなったら前のスライドに戻って確認しましょう。

Pythonプログラムの空欄（ａ）、（ｂ）を埋めてGoogle Colabで実行してみましょう。

Google Colabは次のリンクから開きましょう。

Google Colab

空欄（ａ）、（ｂ）に入る処理を下記の一覧から選んで答えてください。

low = middle + 1

low = middle - 1

high = middle + 1

high = middle - 1

（ａ）に入る命令を答えてください。

（ｂ）に入る命令を答えてください。

（ａ）（ｂ）のヒント

1行前の条件が「 data[ middle ] < target 」です。この条件が成立する場合は、探索する値が現在の中央の値より大きい場合です。

より大きい値を探すときは、変数lowの値を更新します。

二分探索の比較回数を答えよう

次のデータがあります。

16, 29, 32, 51, 57, 87, 90, 103, 111, 145, 147, 153, 155, 157, 165, 194, 220, 240, 301, 312, 314, 332, 349, 397, 402, 428, 453, 493, 545, 551, 553, 559, 586, 701, 707, 726, 755, 784, 785, 794, 811, 855, 874, 890, 896, 919, 926, 948, 990, 995, 1001, 1032, 1037, 1041, 1070, 1155, 1188, 1192, 1198, 1216, 1252, 1256, 1275, 1278, 1311, 1315, 1338, 1342, 1348, 1356, 1358, 1359, 1425, 1452, 1460, 1467, 1489, 1509, 1557, 1598, 1660, 1709, 1732, 1746, 1769, 1772, 1788, 1798, 1804, 1830, 1836, 1922, 1965, 2002, 2022, 2028, 2062, 2064, 2103, 2104, 2107, 2139, 2157, 2195, 2201, 2221, 2253, 2276, 2303, 2316, 2332, 2340, 2341, 2350, 2432, 2436, 2480, 2504, 2522, 2548, 2585, 2591, 2606, 2638, 2651, 2656, 2662, 2665, 2669, 2671, 2683, 2687, 2718, 2728, 2737, 2756, 2769, 2774, 2782, 2850, 2883, 2884, 2890, 2932, 2952, 2955, 2980, 2991, 2992, 2996, 3030, 3053, 3055, 3056, 3065, 3072, 3082, 3138, 3167, 3168, 3212, 3216, 3221, 3244, 3281, 3290, 3297, 3324, 3376, 3392, 3425, 3468, 3490, 3519, 3636, 3640, 3658, 3673, 3687, 3720, 3729, 3731, 3764, 3807, 3826, 3843, 3858, 3863, 3889, 3895, 3909, 3957, 3970, 3980, 4019, 4056, 4065, 4099, 4108, 4165, 4167, 4194, 4195, 4197, 4234, 4240, 4248, 4250, 4257, 4266, 4267, 4270, 4349, 4359, 4368, 4385, 4404, 4410, 4448, 4477, 4483, 4503, 4569, 4589, 4603, 4628, 4643, 4705, 4709, 4757, 4815, 4830, 4848, 4857, 4861, 4938, 4944, 4945, 4965, 5001, 5013, 5045, 5059, 5078, 5081, 5096, 5118, 5152, 5153, 5182, 5184, 5205, 5245, 5254, 5256, 5258, 5265, 5282, 5283, 5369, 5389, 5396, 5402, 5441, 5458, 5460, 5465, 5470, 5506, 5548, 5569, 5574, 5590, 5608, 5609, 5613, 5623, 5634, 5636, 5674, 5682, 5683, 5691, 5695, 5729, 5747, 5764, 5770, 5779, 5781, 5785, 5809, 5824, 5836, 5864, 5869, 5879, 5888, 5899, 5906, 5912, 5920, 5924, 5937, 5946, 5949, 5983, 6000, 6052, 6057, 6064, 6105, 6110, 6113, 6121, 6129, 6180, 6297, 6304, 6323, 6325, 6340, 6341, 6342, 6351, 6363, 6371, 6392, 6404, 6416, 6458, 6479, 6496, 6513, 6527, 6551, 6561, 6576, 6597, 6615, 6618, 6638, 6643, 6648, 6667, 6670, 6689, 6693, 6697, 6737, 6751, 6762, 6777, 6778, 6814, 6847, 6856, 6891, 6895, 6908, 6920, 6933, 6956, 6988, 7006, 7027, 7035, 7041, 7060, 7072, 7107, 7111, 7142, 7172, 7174, 7238, 7241, 7250, 7279, 7304, 7307, 7308, 7310, 7314, 7377, 7386, 7401, 7402, 7428, 7479, 7512, 7536, 7554, 7571, 7574, 7588, 7624, 7627, 7637, 7670, 7687, 7702, 7744, 7751, 7754, 7791, 7804, 7829, 7852, 7904, 7905, 7916, 7917, 7942, 8001, 8016, 8018, 8063, 8071, 8084, 8091, 8139, 8144, 8191, 8194, 8220, 8238, 8245, 8268, 8269, 8294, 8301, 8384, 8388, 8454, 8471, 8494, 8509, 8511, 8517, 8526, 8530, 8572, 8587, 8627, 8640, 8689, 8704, 8746, 8840, 8848, 8850, 8893, 8911, 8963, 9022, 9024, 9029, 9047, 9054, 9087, 9090, 9144, 9149, 9169, 9193, 9210, 9245, 9311, 9340, 9395, 9416, 9483, 9502, 9526, 9536, 9548, 9550, 9551, 9557, 9590, 9601, 9604, 9614, 9619, 9658, 9663, 9670, 9761, 9829, 9859, 9898, 9904, 9938, 9953, 9999, 10033, 10043, 10048, 10064, 10065, 10115, 10136, 10185, 10188, 10193, 10201, 10205, 10210, 10264, 10266, 10270, 10287, 10321, 10322, 10357, 10377, 10386, 10424, 10429, 10436, 10446, 10454, 10456, 10457, 10470, 10508, 10544, 10622, 10635, 10640, 10644, 10650, 10659, 10755, 10810, 10827, 10867, 10877, 10881, 10883, 10906, 10908, 10921, 10953, 10954, 10969, 10973, 10979, 11011, 11025, 11028, 11041, 11082, 11091, 11093, 11129, 11182, 11200, 11207, 11247, 11250, 11262, 11281, 11289, 11312, 11339, 11348, 11357, 11380, 11388, 11402, 11453, 11455, 11463, 11468, 11501, 11506, 11512, 11520, 11542, 11558, 11574, 11594, 11632, 11640, 11651, 11705, 11788, 11796, 11834, 11884, 11894, 11902, 11913, 11918, 11919, 11947, 11989, 12011, 12062, 12097, 12154, 12182, 12197, 12200, 12206, 12222, 12230, 12244, 12313, 12324, 12330, 12338, 12431, 12477, 12491, 12500, 12562, 12596, 12598, 12603, 12618, 12696, 12706, 12715, 12735, 12736, 12741, 12744, 12746, 12753, 12757, 12759, 12760, 12775, 12819, 12820, 12835, 12840, 12847, 12862, 12864, 12895, 12904, 12906, 12924, 12943, 12993, 13008, 13022, 13043, 13113, 13114, 13156, 13175, 13196, 13205, 13215, 13229, 13238, 13242, 13317, 13327, 13332, 13359, 13375, 13417, 13457, 13475, 13485, 13508, 13510, 13536, 13575, 13595, 13602, 13607, 13622, 13633, 13638, 13671, 13700, 13702, 13703, 13714, 13733, 13763, 13799, 13811, 13836, 13855, 13863, 13877, 13909, 13928, 13941, 13944, 14035, 14050, 14062, 14079, 14083, 14085, 14087, 14098, 14103, 14108, 14122, 14175, 14202, 14210, 14259, 14299, 14326, 14346, 14347, 14381, 14386, 14394, 14407, 14412, 14434, 14449, 14464, 14525, 14546, 14549, 14559, 14572, 14584, 14643, 14672, 14697, 14732, 14741, 14742, 14786, 14821, 14832, 14867, 14919, 14934, 14941, 14942, 15025, 15034, 15038, 15065, 15107, 15153, 15183, 15188, 15214, 15253, 15271, 15274, 15289, 15337, 15342, 15393, 15403, 15414, 15423, 15424, 15436, 15473, 15496, 15512, 15522, 15527, 15564, 15623, 15633, 15671, 15683, 15685, 15694, 15710, 15714, 15724, 15732, 15734, 15778, 15789, 15808, 15811, 15827, 15875, 15936, 15952, 15977, 15992, 16029, 16031, 16047, 16066, 16105, 16125, 16134, 16146, 16151, 16205, 16222, 16251, 16261, 16298, 16306, 16316, 16368, 16371, 16390, 16406, 16413, 16430, 16509, 16517, 16519, 16542, 16559, 16572, 16580, 16591, 16608, 16615, 16634, 16708, 16725, 16770, 16775, 16777, 16817, 16831, 16857, 16866, 16870, 16894, 16897, 16918, 16931, 16941, 16984, 16991, 16996, 17023, 17034, 17045, 17061, 17070, 17088, 17092, 17097, 17102, 17120, 17126, 17175, 17181, 17190, 17199, 17237, 17268, 17289, 17305, 17336, 17354, 17365, 17406, 17419, 17420, 17432, 17439, 17442, 17451, 17529, 17539, 17559, 17585, 17592, 17620, 17645, 17646, 17662, 17693, 17779, 17810, 17884, 17893, 17912, 17937, 17941, 17948, 17968, 17973, 17978, 17983, 17993, 18026, 18039, 18058, 18065, 18078, 18108, 18128, 18156, 18164, 18173, 18186, 18217, 18246, 18250, 18256, 18267, 18291, 18366, 18373, 18492, 18497, 18526, 18549, 18554, 18582, 18599, 18600, 18605, 18610, 18611, 18616, 18637, 18689, 18712, 18758, 18825, 18846, 18860, 18869, 18871, 18876, 18877, 18916, 18945, 18947, 18976, 18993, 18998, 18999, 19033, 19042, 19053, 19071, 19082, 19110, 19141, 19159, 19161, 19186, 19232, 19288, 19290, 19312, 19339, 19342, 19343, 19348, 19349, 19361, 19396, 19405, 19413, 19417, 19435, 19444, 19452, 19489, 19512, 19533, 19536, 19559, 19571, 19586, 19615, 19616, 19617, 19633, 19659, 19682, 19683, 19729, 19755, 19763, 19772, 19808, 19838, 19850, 19865, 19877, 19901, 19922, 19950, 19974, 19990

この中から、指定されたデータを探索し比較回数を表示します。

大量のデータがありますが、この中から目的のデータを探してみましょう。

うーん、目がチカチカしてきた⋯。

こういうときほど、Pythonを使って探したほうが良いってことですね。

そうです！こういうときはPythonプログラムで解決しましょう。

今回のプログラムの変更ポイントは以下のとおりです。

変更ポイント1

探索する配列にデータをセットする。

Pythonプログラムで配列データを作成しているところは、18行目「data = generate_array(20, 1, 100)」です。

上記データを利用するために18行目を次のように変更します。

data = [16, 29, 32, 51, 57, 87, 90, 103, 111, 145, 147, 153, 155, 157, 165, 194, 220, 240, 301, 312, 314, 332, 349, 397, 402, 428, 453, 493, 545, 551, 553, 559, 586, 701, 707, 726, 755, 784, 785, 794, 811, 855, 874, 890, 896, 919, 926, 948, 990, 995, 1001, 1032, 1037, 1041, 1070, 1155, 1188, 1192, 1198, 1216, 1252, 1256, 1275, 1278, 1311, 1315, 1338, 1342, 1348, 1356, 1358, 1359, 1425, 1452, 1460, 1467, 1489, 1509, 1557, 1598, 1660, 1709, 1732, 1746, 1769, 1772, 1788, 1798, 1804, 1830, 1836, 1922, 1965, 2002, 2022, 2028, 2062, 2064, 2103, 2104, 2107, 2139, 2157, 2195, 2201, 2221, 2253, 2276, 2303, 2316, 2332, 2340, 2341, 2350, 2432, 2436, 2480, 2504, 2522, 2548, 2585, 2591, 2606, 2638, 2651, 2656, 2662, 2665, 2669, 2671, 2683, 2687, 2718, 2728, 2737, 2756, 2769, 2774, 2782, 2850, 2883, 2884, 2890, 2932, 2952, 2955, 2980, 2991, 2992, 2996, 3030, 3053, 3055, 3056, 3065, 3072, 3082, 3138, 3167, 3168, 3212, 3216, 3221, 3244, 3281, 3290, 3297, 3324, 3376, 3392, 3425, 3468, 3490, 3519, 3636, 3640, 3658, 3673, 3687, 3720, 3729, 3731, 3764, 3807, 3826, 3843, 3858, 3863, 3889, 3895, 3909, 3957, 3970, 3980, 4019, 4056, 4065, 4099, 4108, 4165, 4167, 4194, 4195, 4197, 4234, 4240, 4248, 4250, 4257, 4266, 4267, 4270, 4349, 4359, 4368, 4385, 4404, 4410, 4448, 4477, 4483, 4503, 4569, 4589, 4603, 4628, 4643, 4705, 4709, 4757, 4815, 4830, 4848, 4857, 4861, 4938, 4944, 4945, 4965, 5001, 5013, 5045, 5059, 5078, 5081, 5096, 5118, 5152, 5153, 5182, 5184, 5205, 5245, 5254, 5256, 5258, 5265, 5282, 5283, 5369, 5389, 5396, 5402, 5441, 5458, 5460, 5465, 5470, 5506, 5548, 5569, 5574, 5590, 5608, 5609, 5613, 5623, 5634, 5636, 5674, 5682, 5683, 5691, 5695, 5729, 5747, 5764, 5770, 5779, 5781, 5785, 5809, 5824, 5836, 5864, 5869, 5879, 5888, 5899, 5906, 5912, 5920, 5924, 5937, 5946, 5949, 5983, 6000, 6052, 6057, 6064, 6105, 6110, 6113, 6121, 6129, 6180, 6297, 6304, 6323, 6325, 6340, 6341, 6342, 6351, 6363, 6371, 6392, 6404, 6416, 6458, 6479, 6496, 6513, 6527, 6551, 6561, 6576, 6597, 6615, 6618, 6638, 6643, 6648, 6667, 6670, 6689, 6693, 6697, 6737, 6751, 6762, 6777, 6778, 6814, 6847, 6856, 6891, 6895, 6908, 6920, 6933, 6956, 6988, 7006, 7027, 7035, 7041, 7060, 7072, 7107, 7111, 7142, 7172, 7174, 7238, 7241, 7250, 7279, 7304, 7307, 7308, 7310, 7314, 7377, 7386, 7401, 7402, 7428, 7479, 7512, 7536, 7554, 7571, 7574, 7588, 7624, 7627, 7637, 7670, 7687, 7702, 7744, 7751, 7754, 7791, 7804, 7829, 7852, 7904, 7905, 7916, 7917, 7942, 8001, 8016, 8018, 8063, 8071, 8084, 8091, 8139, 8144, 8191, 8194, 8220, 8238, 8245, 8268, 8269, 8294, 8301, 8384, 8388, 8454, 8471, 8494, 8509, 8511, 8517, 8526, 8530, 8572, 8587, 8627, 8640, 8689, 8704, 8746, 8840, 8848, 8850, 8893, 8911, 8963, 9022, 9024, 9029, 9047, 9054, 9087, 9090, 9144, 9149, 9169, 9193, 9210, 9245, 9311, 9340, 9395, 9416, 9483, 9502, 9526, 9536, 9548, 9550, 9551, 9557, 9590, 9601, 9604, 9614, 9619, 9658, 9663, 9670, 9761, 9829, 9859, 9898, 9904, 9938, 9953, 9999, 10033, 10043, 10048, 10064, 10065, 10115, 10136, 10185, 10188, 10193, 10201, 10205, 10210, 10264, 10266, 10270, 10287, 10321, 10322, 10357, 10377, 10386, 10424, 10429, 10436, 10446, 10454, 10456, 10457, 10470, 10508, 10544, 10622, 10635, 10640, 10644, 10650, 10659, 10755, 10810, 10827, 10867, 10877, 10881, 10883, 10906, 10908, 10921, 10953, 10954, 10969, 10973, 10979, 11011, 11025, 11028, 11041, 11082, 11091, 11093, 11129, 11182, 11200, 11207, 11247, 11250, 11262, 11281, 11289, 11312, 11339, 11348, 11357, 11380, 11388, 11402, 11453, 11455, 11463, 11468, 11501, 11506, 11512, 11520, 11542, 11558, 11574, 11594, 11632, 11640, 11651, 11705, 11788, 11796, 11834, 11884, 11894, 11902, 11913, 11918, 11919, 11947, 11989, 12011, 12062, 12097, 12154, 12182, 12197, 12200, 12206, 12222, 12230, 12244, 12313, 12324, 12330, 12338, 12431, 12477, 12491, 12500, 12562, 12596, 12598, 12603, 12618, 12696, 12706, 12715, 12735, 12736, 12741, 12744, 12746, 12753, 12757, 12759, 12760, 12775, 12819, 12820, 12835, 12840, 12847, 12862, 12864, 12895, 12904, 12906, 12924, 12943, 12993, 13008, 13022, 13043, 13113, 13114, 13156, 13175, 13196, 13205, 13215, 13229, 13238, 13242, 13317, 13327, 13332, 13359, 13375, 13417, 13457, 13475, 13485, 13508, 13510, 13536, 13575, 13595, 13602, 13607, 13622, 13633, 13638, 13671, 13700, 13702, 13703, 13714, 13733, 13763, 13799, 13811, 13836, 13855, 13863, 13877, 13909, 13928, 13941, 13944, 14035, 14050, 14062, 14079, 14083, 14085, 14087, 14098, 14103, 14108, 14122, 14175, 14202, 14210, 14259, 14299, 14326, 14346, 14347, 14381, 14386, 14394, 14407, 14412, 14434, 14449, 14464, 14525, 14546, 14549, 14559, 14572, 14584, 14643, 14672, 14697, 14732, 14741, 14742, 14786, 14821, 14832, 14867, 14919, 14934, 14941, 14942, 15025, 15034, 15038, 15065, 15107, 15153, 15183, 15188, 15214, 15253, 15271, 15274, 15289, 15337, 15342, 15393, 15403, 15414, 15423, 15424, 15436, 15473, 15496, 15512, 15522, 15527, 15564, 15623, 15633, 15671, 15683, 15685, 15694, 15710, 15714, 15724, 15732, 15734, 15778, 15789, 15808, 15811, 15827, 15875, 15936, 15952, 15977, 15992, 16029, 16031, 16047, 16066, 16105, 16125, 16134, 16146, 16151, 16205, 16222, 16251, 16261, 16298, 16306, 16316, 16368, 16371, 16390, 16406, 16413, 16430, 16509, 16517, 16519, 16542, 16559, 16572, 16580, 16591, 16608, 16615, 16634, 16708, 16725, 16770, 16775, 16777, 16817, 16831, 16857, 16866, 16870, 16894, 16897, 16918, 16931, 16941, 16984, 16991, 16996, 17023, 17034, 17045, 17061, 17070, 17088, 17092, 17097, 17102, 17120, 17126, 17175, 17181, 17190, 17199, 17237, 17268, 17289, 17305, 17336, 17354, 17365, 17406, 17419, 17420, 17432, 17439, 17442, 17451, 17529, 17539, 17559, 17585, 17592, 17620, 17645, 17646, 17662, 17693, 17779, 17810, 17884, 17893, 17912, 17937, 17941, 17948, 17968, 17973, 17978, 17983, 17993, 18026, 18039, 18058, 18065, 18078, 18108, 18128, 18156, 18164, 18173, 18186, 18217, 18246, 18250, 18256, 18267, 18291, 18366, 18373, 18492, 18497, 18526, 18549, 18554, 18582, 18599, 18600, 18605, 18610, 18611, 18616, 18637, 18689, 18712, 18758, 18825, 18846, 18860, 18869, 18871, 18876, 18877, 18916, 18945, 18947, 18976, 18993, 18998, 18999, 19033, 19042, 19053, 19071, 19082, 19110, 19141, 19159, 19161, 19186, 19232, 19288, 19290, 19312, 19339, 19342, 19343, 19348, 19349, 19361, 19396, 19405, 19413, 19417, 19435, 19444, 19452, 19489, 19512, 19533, 19536, 19559, 19571, 19586, 19615, 19616, 19617, 19633, 19659, 19682, 19683, 19729, 19755, 19763, 19772, 19808, 19838, 19850, 19865, 19877, 19901, 19922, 19950, 19974, 19990]