【Java -- 算法】二分查找

二分查找算法

1、思想

有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

实现思路：

• 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
• 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
• 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2、二分查找法的优缺点

优点：

• 比较次数少，查找速度快，平均性能好；

缺点：

• 要求待查表为有序表，且插入删除困难。

使用条件：

• 查找序列是顺序结构，有序。

3、java的递归和非递归实现

public class test01 {

public static void main(String args[]) {
int [] array={24,56,68,77,79,93,97};
select1(array,93,0,array.length-1);
select2(array,93);
}

/**
* 二分查找方法一:递归实现
* @param array
*/
private static int select1(int[] array,int target,int low,int high) {
if(low<0||high>array.length-1||low>high){
System.out.println("有错误！！！");
return -1;
}
int middle=(low+high)/2;
if(array[middle]>target){
return select1(array,target,low,middle-1);
}else if(array[middle]<target){
return select1(array,target,middle+1,high);
}else{
System.out.println("递归法实现二分查找： "+array[middle]+"的index是："+middle);
return middle;
}
}
/**
* 二分查找方法二：非递归实现
* @param array
*/
private static int select2(int[] array,int target) {
int left=0;//左
int right=array.length-1;//右
int middle=0;
while(left>=0&&right<array.length&&left<right){
middle=(left+right)/2;
if(array[middle]>target){
right=middle-1;
}else if(array[middle]<target){
left=middle+1;
}else{
System.out.println("非递归法实现二分查找： "+array[middle]+"的index是："+middle);
return middle;
}
}
return -1;
}
}

实例

有一个0-99之间的数组，随便取一个数，每猜一次都告诉你大了还似乎小了直到猜中为止。比如这个数是33

第一次 0-99 中间数是49 49>33
第二次 0-48 中间数是24 24<33
第三次 25-48 中间数是36 36>33
第四次 25-35 中间数是30 30<33
第五次 31-36 中间数是33 33=33
只需要5次就找到了

二分查找针对的是一个有序的数据集合，每次都通过根区间内的中间元素对比，将待查找的区间缩小为之前的一半，知道招到查找的元素，或者区间缩小为 0。

public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;

while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}

return -1;
}

之所以是最简单的实现，因为限制很多，必须是有序的数组并且不能有重复的元素。

• 循环退出条件
  low<=high
• mid的取值
  mid=(low+high)/2这种写法有问题。因为low和high比较大的话，两者之和有可能会溢出。改进的方法是low+(high-low)/2。更近一步的话可以使用位运算符，因为计算机处理位运算符比除法快，low+((high-low)>>1)
• low和high的更新
  low=mid+1 heigh=mid-1 如果直接写low=mid 或者 high=mid可能会发生死循环。比如high=3,low=3，如果a[3]不等于value，就死循环了。

二分查找除了使用循环实现，还可以使用递归，因为其子任务都是找到中间的值跟要找的值做比较

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;

int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return bsearchInternally(a, mid+1, high, value);
} else {
return bsearchInternally(a, low, mid-1, value);
}
}