二分查找，要求集合是有序的，在这个条件基础上，它比顺序查找具有更好的性能。

如果使用伴随数组，只需要struct中有一个key是有序的就行。

需要指出的是，当数组放在磁盘上时，时间复杂度就不再是O(LogN)，而取决于磁盘存取的开销。

源代码：

#include <stdio.h>

typedef int TYPE;

int search(TYPE* arr, int n, int t)
{
    int low = 0;
    int high = n - 1;
    int mid;

    while(low<=high)
    {   
        mid = ( low + high ) / 2;
        if(arr[mid]==t)
        {   
            return mid;
        }   
        else if (arr[mid]<t)
        {   
            low = mid + 1;
        }   
        else
        {   
            high = mid - 1;
        }   
    }   
    return -1; 
}

int main()
{
    TYPE arr[7] = {1, 2, 3, 4, 5, 10, 25};
    TYPE t = 4;
    printf("Is %d in array: %d\n", t, search(arr, sizeof(arr)/sizeof(TYPE), t));
    return 0;
}

二分查找的变种：

1、支持快速插入和删除：由于原始集合是有序的，插入、删除都需要移动平均一半的数组。衍生出散列查找和平衡二叉树。

2、支持磁盘I/O：当数组存在磁盘上时，查找时间取决于磁盘操作所花费的时间。一个有效的方法是B树。