二分搜索 bsearch

二分搜索是常用的搜索方法。

其基本原理是待搜索的元素是经过排序的。通过每次检查排在正中间的那个元素，可以去掉一半的不匹配元素。如此，最多可以通过log2(n)次比较找到要找的元素（或者确认它不存在）。

bsearch 算法

用 C 语言表示的二分搜索 bsearch

int bsearch(const char *key, const char *argv[], int argc){
  int lwb=0, upb=argc-1;    // lower bound and upper bound

  while( upb>=lwb ){
    i = (upb+lwb)/2;
    c = strcmp(key, argv[i]);
    if( c>0 ){
      lwb = i+1;
    }else if( c<0 ){
      upb = i-1;
    }else{
      return i;
    }
  }
  return -1;
}

bsearch in C

#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t item_size, size_t n_items,
              int (*compar)(const void *, const void *));

为了通用，bsearch() 查找的是一个指针，而不是具体元素，同时需要指定单个元素的大小和用于比较的函数。

一种常见的使用情况是下面这样：

typedef struct {
  const char *name;
  int value;
} SomeType;

SomeType items[] = {
  {"a", 1},
  {"b", 2},
  {"z", 9}
};

SomeType *found;
SomeType key = {"k", 0};

int size = sizeof(items[0]);
int count = sizeof(items)/sizeof(items[0]);

found = bsearch(&key, items, size, count);

if( found==NULL ){
  // Not Found
} else {
  int result = found->value;
}