基于线性表的查找----------------二分查找

       线性表不难理解，就是所谓的数组，链表。基于该数据结构常用

的查找方式就是二分查找，时间复杂度是O(log(n))，而不可能使用遍

历的方式查找，那样时间复杂度是O(n),在内核里面使用二分查找的场

景还比较多，所以想总结下二分查找。
-------------------------------------------------------------------------------
一，二分查找我所理解的算法。

 算法:
      <1>,将n个元素分成个数大致相同的两半。
      <2>,取a[n/2]与x的值比较有如下三种结果：
           2.1,如果x = a[n/2],则找到x,算法结束。
           2.2,如果x > a[n/2],则只需在数组a的右半部找。
                   将left = mid + 1,然后转到<1>。
           2.3,如果x < a[n/2],则只需在数组a的左半部找。
                   将right = mid - 1,然后转到<1>。
      <3>,如果没有找到，则返回一个没有找到的标志，算法结束。

--------------------------------------------------------------------------------
二，我眼中的二分查找代码。
   尽管写的比较简单，但整个算法的思想还是体现出来了。

int binary_search(int a[],int lo,int hi,int x)
{
int left = lo;
int right = hi;
int mid = 0;

while (left <= right) {
mid = (left + right) >> 1;
if (x == a[mid])
return mid;
else if (x > a[mid])
left = mid + 1;
else
right = mid - 1;
}

return -1;

}

--------------------------------------------------------------------------------
三，二分查找的扩展。
假如现在排序数组中有出现重复的数字，而我要搜索这重复数字中的第一个。
例如，a[] = {1,2,3,3,3,3,4,5}当要搜索3时返回第一个3的下标。

算法思想：
         可以使用“二分查找嵌套”的思想，首先是找到这个数字，然后在这些
重复的数字中查找第一个。

算法的实现代码如下：

int get_first_k(int a[],int start,int end,int k)
{
            if (start > end)
                return -1;
            int mid = (start + end) >> 1;
            int mid_data = a[mid];

            if (mid_data == k) {
                    if (mid == 0 || (mid > 0 && a[mid-1] != k)) {
                            return mid;
                    }else {
                            end = mid - 1;
                    }
            } else if (mid_data > k) {
                    end = mid - 1;
            } else {
                    start = mid + 1;
            }
        return get_first_k(a,start,end,k);
}

同样，如果是要搜索这排序数组的某个数字，如果这个这个数字有重复，则返回
最后的一个。算法思想是一样的。
--------------------------------------------------------------------------------
四，内核里面二分查找的实现代码分析。

/*
 * bsearch - binary search an array of elements
 * @key: pointer to item being searched for
 * @base: pointer to first element to search
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 *
 * This function does a binary search on the given array. The
 * contents of the array should already be in ascending sorted order
 * under the provided comparison function.
 *
 * Note that the key need not have the same type as the elements in
 * the array, e.g. key could be a string and the comparison function
 * could compare the string with the struct's name field. However, if
 * the key and elements in the array are of the same type, you can use
 * the same comparison function for both sort() and bsearch().
 */
void *bsearch(const void *key, const void *base, size_t num, size_t size,
     int (*cmp)(const void *key, const void *elt))
{
    size_t start = 0, end = num;
    int result;

    while (start < end) {
        size_t mid = start + (end - start) / 2;

        result = cmp(key, base + mid * size);
        if (result < 0)
            end = mid;
        else if (result > 0)
            start = mid + 1;
        else
            return (void *)base + mid * size;
    }

    return NULL;
}

内核里面的二分查找的实现有什么优点呢？
 我觉得可拓展性特别好，就是代码没有写死，只要是想用二分查找的场景

都可以用。

1，类型的可拓展性。人家的函数的形参都是用的void *类型，这说明所有

类型的数组都可以适合，void表示“无”，“无”就表示“任意”，就像

白光是有七色光组成的一样。

2，比较的可拓展性。人家的比较需要自己写比较函数，如何比较由用户自己

决定，比较的方式也通过参数的方式传入到函数里面。

3，查找范围的可拓展性。这地方有一个base参数，说的就是从哪个地方开始

查找。这样用户就可以自己按照想查找的范围进行查找了。
--------------------------------------------------------------------------------
四，学习内核里面的二分查找，我们也可以把内核里面的二分查找的思想和

代码复用到用户态下。
    

下面有一个简单的实例：
    my_bsearch.rar  

----------------------------------------------------------------------------