轉載：http://blog.chinaunix.net/uid-1844931-id-3337784.html
前幾天在論壇上看到有統計說有80%的程序員不能夠寫對簡單的二分法。二分法不是很簡單的嗎？ 這難道不是聳人聽聞？

其實，二分法真的不那么簡單，尤其是二分法的各個變種。 最最簡單的二分法，就是從一個排好序的數組之查找一個key值。 如下面的程序：

#include <iostream>
using namespace std;
int binary_search(int *a,int n,int key)//注意a已按從小到大排序
{int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]==key){return mid;}else if (a[mid]>key){right=mid-1;}else{left=mid+1;}}
return -1;}
int binary_search_first_equal(int *a,int n,int key)//注意a已按從小到大排序
{// 找出第一個與key相等的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>=key){right=mid-1;}else{left=mid+1;}}if (a[left]==key&&left<n){return left;}return -1;}
int binary_search_last_equal(int *a,int n,int key)//注意a已按從小到大排序
{// 找出最后一個與key相等的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>key){right=mid-1;}else{left=mid+1;}}if (a[right]==key&&right>=0){return right;}return -1;}
int binary_search_first_greater_equal(int *a,int n,int key)//注意a已按從小到大排序
{//  查找第一個等于或者大于Key的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>=key){right=mid-1;}else{left=mid+1;}}return left;}
int binary_search_first_greater(int *a,int n,int key)//注意a已按從小到大排序
{//  查找第一個大于Key的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>key){right=mid-1;}else{left=mid+1;}}return left;}
int binary_search_last_less_equal(int *a,int n,int key)//注意a已按從小到大排序
{//  查找最后一個等于或者小于Key的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>key){right=mid-1;}else{left=mid+1;}}return right;}
int binary_search_last_less(int *a,int n,int key)//注意a已按從小到大排序
{//  查找最后一個小于Key的元素int left=0;int right=n-1;while (left<=right){int mid=(left+right)/2;//int mid=left+(right-left)>>1;if (a[mid]>=key){right=mid-1;}else{left=mid+1;}}return right;}void test1()
{int a[5]={1,2,3,4,5};printf(" test1 begins\t");if (binary_search(a,5,3)==2){printf("test passed\n");}else{printf("test failure\n");}
}
void test2()//查找第一個等于key的值
{int a[5]={1,2,3,3,5};printf(" test2 begins\t");if (binary_search_first_equal(a,5,3)==2){printf("test passed\n");}else{printf("test failure\n");}
}
void test3()//查找最后一個等于key的值
{int a[5]={1,2,3,3,5};printf(" test3 begins\t");if (binary_search_last_equal(a,5,3)==3){printf("test passed\n");}else{printf("test failure\n");}}
void test4()//查找第一個大于等于key的值
{int a[5]={1,2,3,3,5};printf(" test4 begins\t");if (binary_search_first_greater_equal(a,5,3)==2){printf("test passed\n");}else{printf("test failure\n");}}
void test5()//查找第一個大于key的值
{int a[5]={1,2,3,3,5};printf(" test5 begins\t");if (binary_search_first_greater(a,5,3)==4){printf("test passed\n");}else{printf("test failure\n");}
}
void test6()//查找最后一個小于等于key的值
{int a[5]={1,2,3,3,5};printf(" test6 begins\t");if (binary_search_last_less_equal(a,5,3)==3){printf("test passed\n");}else{printf("test failure\n");}
}
void test7()//查找最后一個小于key的值
{int a[5]={1,2,3,3,5};printf(" test7 begins\t");if (binary_search_last_less(a,5,3)==1){printf("test passed\n");}else{printf("test failure\n");}
}
void main()
{test1();test2();test3();test4();test5();test6();test7();}

結果：
test1 begins test passed
test2 begins test passed
test3 begins test passed
test4 begins test passed
test5 begins test passed
test6 begins test passed
test7 begins test passed
請按任意鍵繼續…