二分搜尋法(binary search)搜尋已排序過的一串資料做快速搜尋。
資料在由小排到大的情況,搜尋值與中間值不同,且搜尋值比中間值為大就可以做判斷往上搜索還是往下搜索。
在資料經過排序:中間值往上的資料全都比搜尋值還小,所以就可以直接往下搜尋這個範圍的值。
反之搜尋值比中間值為大:中間值往上的資料全都比搜尋值還大,我們不需要往下去尋找中間值以後的值。
舉例來說,現在我們需要在下面這些資料中搜尋數值 35:
往下 中間值 往上
3 8 14 20 23 35 41 44 55 57 72 88 91
過程一找出中間值 41 與35 比大小為小
過程二往下找中間值為20與35比大小為大
過程三往上找中間值為23與35比大小為大
過程四當只剩兩的數值時相比後就可得到資料為35
private void button4_Click(object sender, EventArgs e)
{
int temp = 0;
int[] intArray = { 11, 23, 34, 46, 53, 16, 72, 85, 3, 96, 4, 74, 2, 39 };
//從小排到大
for (int i = 0; i < intArray.Length; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if (intArray[j + 1] < intArray[j])
{
temp = intArray[j + 1];
intArray[j + 1] = intArray[j];
intArray[j] = temp;
}
}
}
int low = 0, high = intArray.Length - 1;
int search = 2;
while (low <= high)
{
int mid = (low + high) / 2; //資料二分
if (intArray[mid] == search)
{
MessageBox.Show("取出搜索值" + intArray[mid].ToString());
low = 9;
}
else if (intArray[mid] > search)
{
high = mid - 1;
}
else if (intArray[mid] < search)
{
low = mid + 1;
}
}
}
