二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。 C語言實現如下： [cpp] #include <stdio.h> void display(int array[],int size){ printf("the array is:"); int i; for(i=0;i<size;i++){ printf("%d ",array[i]); } printf("\n"); } void middle(int array[],int size,int num){ int first=0,last=size-1,middle=0; while(first <= last){ middle = (first+last)/2; if(array[middle] > num){ last = middle-1; }else if(array[middle] < num){ first = middle+1; }else{ printf("this num index is %d\n",middle); return; } } printf("this num is not found\n"); } int main(void){ int array[10]={1,2,46,67,69,120,121,262,456,500}; display(array,10); middle(array,10,121); return 0; }
