学步园

Binary Search可以说是最简单的排序了，看书发现其实有两种Binary Search，一般常见的那种效率稍微低一点点。

直接看看两个我认为比较简单的程序(还有两种我有点看不惯)，比较了两种方法的时间

binary_search_0(int v, int a[], int n)在while循环中要做两次检测

binary_search_0(int v, int a[], int n)在while循环中只做一次检测

#include<stdio.h><br /> #include<time.h><br /> #define INTS_LENGTH 300000<br /> //int v 要查找的数<br /> //int a[] 已经排好序的数组<br /> //int n 要进行比较的数组的下标从0到n-1<br /> int binary_search_0(int v, int a[], int n);<br /> int binary_search_1(int v, int a[], int n);</p> <p>int main(void) {<br /> int index;<br /> clock_t time_taken;<br /> int a[INTS_LENGTH];<br /> int i;<br /> for(i = 0; i < INTS_LENGTH; i++) {<br /> a[i] = i;<br /> }<br /> int n = -1;<br /> //Test time binary_search_0<br /> for(i = 0, time_taken = clock(); i < INTS_LENGTH; i++) {<br /> index = binary_search_0(n, a, INTS_LENGTH);<br /> }<br /> time_taken = clock()-time_taken;<br /> if(index < 0) {<br /> printf("%d not found!/n", n);<br /> } else {<br /> printf("%d found at index %d/n", n, index);<br /> }<br /> printf("binary_search_0 took %ul clocks(%ul seconds)/n",<br /> (unsigned long)time_taken,<br /> (unsigned long)(time_taken/CLOCKS_PER_SEC));<br /> //Test time binary_search_1<br /> for(i = 0, time_taken = clock(); i < INTS_LENGTH; i++) {<br /> index = binary_search_1(n, a, INTS_LENGTH);<br /> }<br /> time_taken = clock()-time_taken;<br /> if(index < 0) {<br /> printf("%d not found!/n", n);<br /> } else {<br /> printf("%d found at index %d/n", n, index);<br /> }<br /> printf("binary_search_1 took %ul clocks(%ul seconds)/n",<br /> (unsigned long)time_taken,<br /> (unsigned long)(time_taken/CLOCKS_PER_SEC));<br /> return 0;<br /> }<br /> int binary_search_0(int v, int a[], int n){<br /> int low, high, mid; low = 0;<br /> high = n-1;<br /> while(low <= high) {<br /> mid = (low+high)/2;<br /> if(a[mid] < v) {<br /> low = mid+1;<br /> } else if(a[mid] > v) {<br /> high = mid-1;<br /> } else {<br /> return mid;<br /> }<br /> }<br /> return -1;<br /> }<br /> int binary_search_1(int v, int a[], int n) {<br /> int low, high, mid;<br /> low = 0;<br /> high = n - 1;<br /> mid = (high+low)/2;<br /> while(low <= high && v != a[mid]) {<br /> if(a[mid] > v) {<br /> high = mid - 1;<br /> } else {<br /> low = mid + 1;<br /> }<br /> mid = (high+low)/2;<br /> }</p> <p> if(v == a[mid]) {<br /> return mid;<br /> } else {<br /> return -1;<br /> }<br /> }<br />