C语言-不对称边界实现二分法查找

本文主要是介绍C语言-不对称边界实现二分法查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

`C` 语言-不对称边界实现二分法查找

问题描述

对一个已经排序的整数表执行二分查找。函数的输入包括一个指向表头的指针，表中的元素，以及待查找的数值，函数的输出是一个指向满足查找要求的元素的指针，当未查找到要求的数值时，输出一个 NULL 指针。

不对称边界

用第一个如界点和第一个出界点来表示一个数值范围

实现

方法一

int bsearch(int *t, int n, int x)
{int lo;int hi;int mid;lo = 0; /* 第一个入界点*/hi = n; /* 第一个出界点 */while(lo < hi){mid = (lo + hi) /  2;if(x < t[mid])hi = mid;                      /* 第一个出界点*/else if(x > t[mid])lo = mid + 1;                  /* 第一个入界点 */elseretuan t + mid;                /* 找到了 */}return NULL;                           /* 没找到 */
}

在很多机器上下标运算比指针运算慢。我们可以把， t + mid 的存储在一个局部变量中，这样就不需要每次都计算，从而可以稍微减少一些内存

int bsearch(int *t, int n, int x)
{int lo;int hi;int mid;int * p;lo = 0; /* 第一个入界点*/hi = n; /* 第一个出界点 */while(lo < hi){mid = (lo + hi) /  2;p = t + mid;if(x < *p)hi = mid;                      /* 第一个出界点*/else if(x > *p)lo = mid + 1;                  /* 第一个入界点 */elseretuan p;                      /* 找到了 */}return NULL;                           /* 没找到 */
}

进一步减少寻址计算，这可以在整个程序中使用指针代表下标，

int bsearch(int *t, int n, int x)
{int *lo;int *hi;int *mid;lo = t;      /* 第一个入界点*/hi = t + n;  /* 第一个出界点 */while(lo < hi){mid = (lo + hi) /  2;if(x < *mid)hi = mid;                      /* 第一个出界点*/else if(x > *mid)lo = mid + 1;                  /* 第一个入界点 */elseretuan mid;                    /* 找到了 */}return NULL;                           /* 没找到 */
}

仔细思考一下

mid = (lo + hi) / 2

指针加指针这个是非法的！！！！！

mid = lo + (hi - lo) / 2

将除法运算转换为移位运算

mid = lo + (hi - lo) >> 2;

感觉优化完了，，，

算术运算符的优先级大于移位运算符！！！！！

mid = lo + ((hi - lo) >> 2)

所以最终的表达式为

int bsearch(int *t, int n, int x)
{int *lo;int *hi;int *mid;lo = t;      /* 第一个入界点*/hi = t + n;  /* 第一个出界点 */while(lo < hi){mid = lo + ((hi - lo) >> 1);if(x < *mid)hi = mid;                      /* 第一个出界点*/else if(x > *mid)lo = mid + 1;                  /* 第一个入界点 */elseretuan mid;                    /* 找到了 */}return NULL;                           /* 没找到 */
}