折半查找,二分法查找
static int binSearch(int value) {
int upperBound, lowerBound, mid;
upperBound = arr.Length-1;
lowerBound = 0;
while(lowerBound <= upperBound) {
mid = (upperBound + lowerBound) / 2;
if (arr[mid] == value)
return mid;
else
if (value < arr[mid])
upperBound = mid - 1;
else
lowerBound = mid + 1;
}
return -1;
}
前提是这个集合是一个有序的组合，不然就不可以折半去找
折半的原理基本上就是把一个有序的集合从中间拆成两半，然后看中间序号的元素是否大于你要查找的值，如果小于就跳到后半段，从后半段的中间序号开始查
举例
想象你正在试图猜测一个朋友选出的1到100之间的数。对于你做出的每一次猜测，朋友告诉你是否猜到了正确的数字，或者你的猜测过大，又或者过小。最佳策略是选择50作为第一个猜测目标。如果猜测过大下一个你就猜25。如果50过小你再猜75。每一次猜测，你应当选择较小的范围或者较大的范围（由你的猜测是过大或过小而定）的中间点作为下一个猜测目标。只要遵守这个策略，你将最终猜到正确的数字。图4.1展示了在选定的数字是82的情况下这个方法的工作情况。