2. left = 0, right = n - 1
3. middle = (left + right) / 2
4.
searchnum > list[middle], left = middle + 1
searchnum = list[middle], return middle
searchnum < list[middle], right = middle - 1
5.
- 建立終止遞回呼叫的條件
- 建立遞回呼叫,使得每一次的呼叫更進一步接近解答
#include <stdio.h> #include <stdlib.h> #include <math.h> int binsearch(int list[], int searchnum, int left, int right); int main(int argc, char *argv[]) { int searchnum, left, right, pos; int list[] = {11, 22, 33, 44, 55, 66, 77, 88, 99}; printf("Enter the numbfer you want to search: "); scanf("%d", &searchnum); left = 0; right = (sizeof(list)/sizeof(list[0])) - 1; pos = binsearch(list, searchnum, left, right); if (pos == -1) printf("not found\n"); else printf("found pos: %d\n", pos); return 0; }
#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1) int binsearch(int list[], int searchnum, int left, int right) { int middle; if (left <= right) { middle = (left + right) / 2; switch(COMPARE(list[middle], searchnum)) { case -1: return binsearch(list, searchnum, middle + 1, right); case 0: return middle; case 1: return binsearch(list, searchnum, left, middle - 1); } } return -1; }
沒有留言:
張貼留言