- 论坛徽章:
- 15
|
本帖最后由 yulihua49 于 2016-10-27 14:47 编辑
那个.h无关紧要,就是这两个函数的原型。
lowerBound查找指定KEY等值元素下标最小的一个。返回找到的下标号,0开始。找不到返回-1;
upperBound查找>KEY的下标最小的一个。返回找到的下标号,0开始。找不到返回-1
lowerBound和upperBound确定了重复元素的上下界。
由于是通用算法,函数并不知道key和data具体的数据类型(一般二者类型相同),只能以void表示之。
需要使用者提供比较函数compare,在这个函数里按照你自己的数据结构和需求进行比较。
data>key 返回正数,=返回0,<返回负数。
其他需求,如>=,<=,<,等等可以用这两个函数组合出来:
- // <key的最后元素
- int less_than(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
- {
- int ret;
- if(0>(ret=lowerBound(key,data,data_siz,cmp)) &&
- 0>(ret=upperBound(key,data,data_siz,cmp))) {
- ret=data_siz;
- }
- return --ret;
- }
- // <=key的最后元素
- int less_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
- {
- int ret;
- if(0>(ret=upperBound(key,data,data_siz,cmp)))
- ret=data_siz;
- return --ret;
- }
- // >=key的第一个元素
- int great_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
- {
- int ret;
- return (ret=lowerBound(key,data,data_siz,cmp))>=0?ret:
- upperBound(key,data,data_siz,cmp);
- }
复制代码
这套函数也可以处理无重复数组,只是效率偏低,基本函数每个节点进行2次比较,派生函数多达4次。
所以还有一套针对无重复值排序数组的函数,每个节点只比较1次。
|
|