整数が昇順に整列された大きさN(10)の配列s (data)に整数keyがあるかを判定する。ある場合は、インデックスを示す。なければ、ないとプリントする。

入力：整数key
出力：配列sに整数keyがある場合は、インデックスを出力。ない場合も、その旨、出力

<実行例>

探索キーを入力してください :14
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
14 is found in s[5]

探索キーを入力してください :23
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
The element 23 is not in s

基本的な部分 (自分で言葉にして、確認しよう）

1. low = 0, high = N-1, mid = (low+high)/2 とする。.5は切り捨てる。　（初期化）
2. low > high なら、終了条件2
3. S[mid] == Key なら、終了条件１
4. そうでないとき、Key < S[mid] ならhigh=mid-1、A[mid] < Key ならlow = mid+1　として、2へ

二分探索をプログラムせよ。（STEP2.1の探索部分を、binary_searchに取り替えなさい）

print文(Cではprintf)を差し込んで、実行中の変数low, high, midの値を確認しよう。納得しよう。デバッグの定番作業です。

解答例

#include <stdio.h>

#define N 10 /* 配列のサイズ */ /* マジックナンバーにならないように。定数をばらまかない */
int s[N] = {1,3,4,8,13,14,18,20,21,25};

void print_data (void);  /* 配列のプリント */
int binary_search (int); /* 引数はintのキー。 見つけた場合の添え字を戻す。*/

int main (void) {
    int x; /* Key */ /* C1 */
    int i; /* なぜかlong iとなっている人がいますが、int iで十分 */ /* Keyの位置 戻り値 */

    printf("探索キーを入力してください :");
    scanf("%d", &x);

    print_data();

    i = binary_search(x); /* 検索せよ。戻り値をiに代入 */

    /* iの値をチェック */
    if(i == -1 ) /* 見つけていない */
         printf("The element %d is not in s\n", x);
    else
         printf("%d is found in s[%d]\n", x,i);


    return 0;
}

void print_data (void) {
    int i;

    for (i = 0; i < N ; i++)
        printf("s[%d] = %d \n", i, s[i]);
}

/* binary_searchを自作しなさい */
/* 疑似コードを参考に */
int binary_search(int key) {

    int low = 0 ; /* 上側 */
    int high = N - 1; /* 最後の要素にあたる */ /* 下側 */
    int mid; 

    while (low <= high) {
        mid = (low + high) /2; /* .5は切り捨て。フロア関数となる */
        printf("low = %2d, high = %2d, mid = %2d \n", low, high, mid); /* チェック */
        if (s[mid] == key ) {  /* 発見 */
           return (mid);
        }
        if (s[mid] > key)     /* keyは、midより上にある。下側のhighを引き上げよう */
           high = mid - 1;
        else
           low = mid + 1 ;
    }

    return -1;
}

STEP 2.2 (二分探索）