数据结构之对分查找算法

      一 、前提条件：对分查找的前提是待查找的数据必须是有序的

     二、思想：对分查找是一种效率很高的查找方法，但被查找的数据必须是有序（例如非递减有序）的。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。

        在数组中的数据是有序的，如果是增序的，是指下标越小的数组元素中存储的数据也越小，减序则相反。设数组变量d中存储了n个互不相同的数据，则数组变量d中的数据是增序时，有：           d(1)<d(2)<…d(i)<d(i+1)<…<d(n-1)<d(n)

   三、优势             由于对分查找没查找一次，查找范围就将缩小一半，因此效率要远远高于顺序查找。

  C语言代码实现：    //BinarySearch.h #ifndef BINARYSEARCH_H

#define BINARYSEARCH_H

#define Notfound -1

#include<stdio.h>

int BinarySearch(int *,int ,int );

#endif

//BinarySearch.c

#include"Binarysearch.h"

int BinarySearch(int array[] , int x, int size)

{

int low=0;

int high = size-1;

int mid;

while(low<=high)

{

mid = (low + high)/2;

if(array[mid]<x)

{

 low = mid + 1;

}

else if(array[mid]>x)

{

 high=mid-1;

}

else

return mid;

}

return Notfound;

}

//main.c

#include"BinarySearch.h"

int main()

{

int array[] = {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11};

    int size = sizeof(array)/sizeof(int);

int x = 5;

int index = BinarySearch(array,x,size);

printf("the index is %d\n",index);

return 0;

}