/** 編寫一個函數，對一個已排序的整數表執行二分查找。* 函數的輸入包括各異指向表頭的指針，表中的元素個數，以及待查找的數值。* 函數的輸出時一個指向滿足查找要求的元素的指針，當未查找到要求的數值時，輸出一個NULL指針* 用兩個版本實現，一個用的是數組小標，第二個用的是指針* 他們均采用了不對稱邊界* Copyright (c) 2012 LiMing Author: LiMing 2012-06-21 referenced C Traps and Pitfaills Chinese Edition Page 132-137* * 查找的元素為x，數組下表是k，開始時0 <= k < n* 接下來縮小范圍lo <= k < hi,* if lo equals hi, we can justify the element "x" is not in the array* */ #include <stdio.h>int array[] = { 0,1,2,3,4,5,6,7 };int *bsearch_01(int *t, int n, int x);int *bsearch_01(int *t, int n, int x) {int lo = 0;int hi = n;while(lo < hi){//int mid = (hi + lo) / 2;int mid = (hi + lo) >> 1;if(x < t[mid])hi = mid;else if(x > t[mid])lo = mid + 1;elsereturn t + mid; }return NULL; }int *bsearch_02(int *t, int n, int x);int *bsearch_02(int *t, int n, int x) {int lo = 0;int hi = n;while(lo < hi){//int mid = (hi + lo) / 2;int mid = (hi + lo) >> 1;int *p = t + mid; //用指針變量p存儲t+mid的值，這樣就不需要每次都重新計算if(x < *p)hi = mid;else if(x > *p)lo = mid + 1;elsereturn p; }return NULL; }//進一步減少尋址運算 /** Suppose we want to reduce address arithmetic still further * by using pointers instead of subscripts throughout the program.* * */ int *bsearch_03(int *t, int n, int x);int *bsearch_03(int *t, int n, int x) {int *lo = t;int *hi = t + n;while(lo < hi){//int mid = (hi + lo) / 2;int *mid = lo + ((hi - lo) >> 1);if(x < *mid)hi = mid;else if(x > *mid)lo = mid + 1;elsereturn mid; }return NULL; }/** The resulting program looks somewhat neater because of the symmetry* */ int *bsearch_04(int *t, int n, int x);int *bsearch_04(int *t, int n, int x) {int lo = 0;int hi = n - 1;while(lo <= hi){//int mid = (hi + lo) / 2;int mid = (hi + lo) >> 1;if(x < t[mid])hi = mid - 1;else if(x > t[mid])lo = mid + 1;elsereturn t + mid; }return NULL; }int main(int argc, char **argv) {int * ret = NULL;int *ret2 = NULL;int *ret3 = NULL;int *ret4 = NULL;ret = bsearch_01(array, 8, 3);ret2 = bsearch_02(array, 8, 6);ret3 = bsearch_03(array, 8, 4);ret4 = bsearch_04(array, 8, 2);printf("The result is %d\n", *ret);printf("The result is %d\n", *ret2);printf("The result is %d\n", *ret3);printf("The result is %d\n", *ret4);printf("hello world\n");return 0; }

總結

以上是生活随笔為你收集整理的C语言二分查找法（指针和数组实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。