二分探索法

二分探索法は配列を用いた逐次探索に分割統治法を適用した探索手続きを用いること。

次のプログラムは配列による記号表を二分探索で実現したもの。

#include <stdlib.h>
#include "Item.h"
#include "ST.h"

static Item *st;
static int N;

void STinit(int maxN)
{
    st = malloc((maxN)*sizeof(Item));
    N = 0;
}

int STcount()
{
    return N;
}

void STinsert(Item item)
{
    int j = N++;
    Key v = key(item);
    while (j>0 && less(v, key(st[j-1]))) {
        st[j] = st[j-1];
        j--;
    }
    st[j] = item;
}

Item search(int l, int r, Key v)
{
    int m = (l+r)/2;
    if (l > r)
        return NULLitem;
    if (eq(v, key(st[m])))
        return st[m];
    if (l == r)
        return NULLitem;

    if (less(v, key(st[m])))
        return search(l, m-1, v);
    else
        return search(m+1, r, v);
}

Item STsearch(Key v)
{
    return search(0, N-1, v);
}

Item STselect(int k)
{
    return st[k];
}

void STsort(void (*visit)(Item))
{
    int i;
    for (i = 0; i < N; i++)
        visit(st[i]);
}

二分探索法の性質
二分探索法では成功あるいは不成功のどちらの場合も比較は{log2N](床関数)　+ 1回以下になる。