二分法查找

（1）确定该区间的中点位置：mid=（low+high）/2    

min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置

（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：

如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中。这时high=mid-1

如果R[mid].key<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。这时low=mid+1

如果R[mid].key=a，则查找成功。

（3）下一次查找针对新的查找区间，重复步骤（1）和（2）

（4）在查找过程中，low逐步增加，high逐步减少，如果low>high，则查找失败。

 

 

平均查找长度=Log2⁽ⁿ⁺¹⁾-1，时间复杂度O（logn）

 查找不成功时和给定值的关键字比较个数最多不超过logn+1.

注：虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，所以二分法比较适用于顺序存储结构。为保持表的有序性，在顺序结构中插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。

所以说用折半查找时序列必须是有序的！

 public class BinarySearch {
/**
* 二分查找
* 简介: 在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列已排序，则该数左边的数一定都小于要搜寻的对象，
* 所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。
* @param nums 待查找数组
* @num 待查找数
*/
public static int search(int[] nums, int num) {
int low = 0;
int high = nums.length - 1;
 
while (low <= high) {
int mid = (low + high) / 2;

//与中间值比较确定在左边还是右边区间,以调整区域
if (num > nums[mid]) {
low = mid + 1;
} else if (num < nums[mid]) {
high = mid - 1;
} else {
return mid;
}
}
 
return -1;
}


//二分查找的实现
public static void main(String[] args) {
 
int[] nums = { 2, 5, 11, 3, 22, 6, 91, 13, 35, 4 };
//对数组进行排序
QuickSort.sort(nums, 0, nums.length-1);

int find = BinarySearch.search(nums,5);

if (find != -1) {
System.out.println("找到数值于索引" + find);
} else {
System.out.println("找不到数值"); 
}
}
}