二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
原理：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，
1. 如果x=a[n/2]则找到x，算法终止；
2. 如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x
3. 如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索
写法一：采用递归法
代码语言：javascript复制/// <summary>
/// 二分法查找,二分查找的条件是原数组有序
/// 没有找到，返回-1；找到了，则返回索引
/// </summary>
/// <param name="arr">数组</param>
/// <param name="low">开始索引</param>
/// <param name="height">结束索引</param>
/// <param name="value">要查找的对象</param>
static int BinarySearch(int[] arr, int low, int high, int value)
{
if (arr == null || arr.Length == 0 || low >= high)
{
return -1;
}
int mid = (low high) / 2;
if (value == arr[mid]) //刚好找到对象，返回索引
{
return mid;
}
else if (value > arr[mid]) // 要查找的对象在右边
{
return BinarySearch(arr, mid 1, high,value);
}
else //要查找的对象在左边
{
return BinarySearch(arr, low, mid - 1, value);
}
}写法二：
代码语言：javascript复制 static int BinarySearch2(int[]arr,int value)
{
int low = 0, high = arr.Length - 1,mid=0;
while (low <= high)
{
mid = (low high) / 2;
if(value== arr[mid])
{
return mid;
}
if (value > arr[mid])//在右侧
{
low = mid 1;
}
else//在左侧
{
high = mid - 1;
}
}
return -1;
}运行结果
代码语言：javascript复制 static void Main(string[] args)
{
Console.WriteLine($"数据算法");
var arr1 = GetArrayData(8, 1, 22);
Console.WriteLine($"生成未排序数据arr1：{ShowArray(arr1)}");
//var arr2 = BubbleSort(arr1);
//Console.WriteLine($"冒泡排序：{ShowArray(arr2)}");
var arr3 = SelectSort(arr1);
Console.WriteLine($"选择排序arr3：{ShowArray(arr3)}");
var val = arr3[3];
var index= BinarySearch(arr3, 0, arr1.Length - 1,val);
Console.WriteLine($"{val}在 arr3中出现的索引位置是{index}");
var val2 = arr3[4];
var index2 = BinarySearch2(arr3, val2);
Console.WriteLine($"{val2}在 arr3中出现的索引位置是{index2}");
Console.ReadLine();
}
