二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,有点类似分治的思想。二分查找针对的是一个有序的数据集合,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。


public static int BinarySearch(int[] array, int target) 
{ 
	int left = 0; 
	int right = array.Length - 1; 
	while (left <= right) 
	{ 
		int mid = left + (right - left) / 2; // 防止整数溢出 
		if (array[mid] == target) 
		{ 
			return mid;
		} 
		else if (array[mid] < target) 
		{
			left = mid + 1;
		} 
		else 
		{ 
			right = mid - 1; 
		} 
	} 
	// 如果没找到目标,返回-1 
	return -1; 
}