【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);
  }
}