折半查找，也叫二分查找，當在一個數組或集合中查找某個元素時，先定位出中間位置元素，如果要查找的元素正好和該中間位置元素相等，通過一次查找，就能找到匹配元素；如果要查找的元素小於該中間位置元素，就拋棄後面一半的元素，在前面一半的元素中再定位出中間位置元素，如此反復，直到找到匹配元素；如果要查找的元素大於該中間位置元素，就拋棄前面一半的元素，在後面一半的元素中定位出中間位置元素，如此反復。
面臨的第一個問題是：中間位置元素如何定位？在折半查找中規定：當元素個數是奇數，比如有3個元素，中間位置元素是索引為1的元素；當元素個數是偶數，比如有4個元素，索引為1和2的元素理論都是中間位置元素，但在折半查找中，把後面這個，即索引為2的元素視為中間位置元素。
面臨的第二個問題是：由於，要查找的元素和中間位置元素之間需要比較，我們在比較之前，勢必要讓數組按升序或降序來排列。
自定義一個類，該類維護著一個int[]類型數組，通過構造函數確定數組長度和對數組進行排序，並提供打印數組元素的方法，以及折半算法。
public class MyArray{private int[] arr;//內部維護著一個數組private static Random r = new Random();//用它來生成數組的隨機元素//通過構造函數來確定內部數組的長度，並生成數組的隨機元素,並對數組元素排序public MyArray(int size){arr = new int[size];for (int i = 0; i < size; i++){arr[i] = r.Next(1, 100);}Array.Sort(arr);}//折半查找算法 返回查找元素的索引位置public int HalfSearch(int key){int low = 0;//低點，初始值設置成最低點，即索引0int high = arr.Length - 1;//高點，初始值設置成最高點，即索引數組最後一個位置//如果數組元素個數是偶數，比如4個，索引2和3都是中間位置，用以下算法中間位置指向索引3//如果數組元素個數是奇數，比如3個，索引1是中間位置，用以下算法中間位置指向索引1int middle = (low + high + 1)/2;int location = -1;//找不到就返回-1//循環，找不到就一直查找do{//每次循環，把低點和高點位置的元素打印出來Console.WriteLine(PrintSectionElements(low, high));Console.WriteLine();//如果要查找元素是中間位置的元素，就返回中間位置這個索引if (key == arr[middle]){location = middle;}else if (key < arr[middle]) //如果要查找元素小於中間位置元素，把中間位置前面的索引設為高點{high = middle - 1;}else//如果要查找元素大於中間位置元素，把中間位置後面的索引設為低點{low = middle + 1;}//如果代碼運行到此處，說明還沒有找到匹配元素，由於以上重新設置了低點或高點，所以這裡也要重新設置中間位置middle = (low + high + 1)/2;} while ((low <= high) && (location == -1));return location;}//打印2個位置間的數組元素public string PrintSectionElements(int low, int high){string temp = "";//對於2個位置間的元素打印出元素並跟上一個空格位置for (int i = low; i <= high; i++){temp += arr[i] + " ";}return temp;}//重寫ToString方法，把數組所有的元素都打印出來public override string ToString(){return PrintSectionElements(0, arr.Length - 1);}}
以上，折半查找的目的是找到匹配元素在數組中的索引位置，為此，通過需查找元素和中間位置元素大小的比較，不斷地調整低點、高點和中間位置。另外，在C#中，1/2的結果是0。
客戶端。
class Program{private static int key; //需查找元素private static int position;//匹配元素所在的位置static void Main(string[] args){MyArray myArray = new MyArray(7);//把所有元素打印出來Console.WriteLine(myArray);Console.WriteLine("請輸入需要查找的元素或輸入-1退出 ");key = Convert.ToInt32(Console.ReadLine());Console.WriteLine();while (key != -1){//調用折半算法得出所需查找元素的位置position = myArray.HalfSearch(key);if (position == -1) //說明沒有找到需要匹配的元素{Console.WriteLine("沒有找到元素{0}", key);}else{Console.WriteLine("在{0}號位置查到元素{1}", position, key);}Console.WriteLine("請輸入需要查找的元素或輸入-1退出 ");key = Convert.ToInt32(Console.ReadLine());Console.WriteLine();}}}
用時間復雜度來描述折半查找的效率
假設一個數組有1023個元素，由於可以表示成"1023=2ⁿ-1"等式，所有n=10。對該數組每進行一次折半，相當於除以2，也就是說，在該數組中查找某個元素，最多需要10次，就可以查到匹配元素。
對於"2ⁿ-1"這個表達式，當n=30，就表示10億，使用折半查找，10億個元素最多需要30次就能找到匹配元素。而使用線性查找需要平均5億次的查找。2種算法的效率由此可見一斑。
把折半查找、二分查找的時間復雜度寫成O(log n)，稱為"對數運行時間",讀為"對數階"。
“查找與排序”系列包括：
你的程序死循環了，當沒有這個數的時候
if(n>a[c])d=c+1;
if(n<a[c])b=c+1;
應該是d=c-1 !
還有一點，就是最後判斷有沒有這個數的時候，改成if(b>=d)才可以！
排序：
#include<stdio.h>
#define N 10
void Display(int *a, int n)
{
int i;
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
void SelectionSort(int *a, int n)
{
int i, j, index, value;
for (i = 0; i < n - 1; i ++) {
index = i;
value = a[i];
for (j = i + 1; j < n; j ++)
if (value > a[j]) {
index = j;
value = a[j];
}
a[index] = a[i];
a[i] = value;
Display(a, n);
}
}
void main()
{
int a[N],i ;
for(i=0;i<N;i++)
a[i]=N-i;
Display(a, N);
SelectionSort(a, N);
}
折半查找：
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
/* 假定a是排好序的 */
/* mustbe(start, end, number)，因為a[start..end]就是整個數組a[0..LEN-1] */
while (start <= end) {
/* mustbe(start, end, number)，因為一開始進入循環時是正確的，每次循環也都維護了這個條件 */
mid = (start + end) / 2;//取a數組中間的值，與number比較
if (a[mid] < number)
/* 如果a數組中間值小於number，那麼number一定要在mid後的後半段數組中，所以我們就將mid+1，將這個作為start，number必然在後半段數組a[mid+1,end]中*/
start = mid + 1;
else if (a[mid] > number)
/如果a數組中間值大於number，那麼number一定在mid前的前半段數組中，那麼應該將mid-1，這個mid-1就是前半段數組的最後一個元素 */
end = mid - 1;
else
/* a[mid] == number，說明找到了 */
return mid;
}
/*
* mustbe(start, end, number)一直被循環維護著，到這裡應該仍然成立，在a[start..end]范圍之外一定不存在number，
*......余下全文>>
