折半查找又叫二分查找，从中间开始查找，这个适用于有序的数据表。听别人说一个面试官，给面试者10次机会，猜他想到的一个词。这个也是用到了折半查找的思想（应该都玩过这个游戏吧，你问别人问题，别人只能回答是或者不是，是生物吗，能走路吗，有羽毛吗。。。），想想也没有那么难。
// 非递归折半 int binary_search(int search_table[],int key) { // 最低位置索引low、最高位置索引high、中间位置索引mid // 中间位置的可能情况 // length为奇数时，mid 为正中间位置 mid的左侧和右侧用于同样数目的元素 // length为偶数时，mid为正中间往左的那一个元素 正中间为小数，正中间往左的那一个位置才是(Low+High)/2 // low与high的关系 // 正常情况下low<high // low==high时，仅剩下最后一个需要判断的元素，此元素可能与key相同，也可能不同 // low>high 未找到与key相同的元素 int low=0; int high=search_table.length-1; int mid=(low+high)/2; while(low<=high){ mid=(low+high)/2; //找到与key相等的一个元素位置 if(search_table[mid]==key) return mid; if (search_table[mid]>key) high=mid-1; else low=mid+1; } return -1; } //递归折半 int binary_search(int search_table[],int low,int high,int key) { if (low>high) return -1; int mid=(low+high)/2; if (search_table[mid]==key) return mid; if (search_table[mid]<key) return binary_search(search_table,low,mid-1,key); else return binary_search(search_table,mid+1,high,key); }
