疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

排序算法之 二分法查找


 

   

  算法:

  当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的(如果数据是无序的,可以调用Arrays.sort(数组变量名)进行排序)。现在我们假定数组是有序的,至于排序的算法我们会一一讲述。

  二分查找主要思想是:(设查找的数组区间为array[start, end])

  (1)确定该期间的中间位置K (=(start+end)/2)

  (2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。

  区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,end]>T;

  故新的区间为array[start,……,K-1]b.array[k]

  每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间缩小一半。递归找,即可,时间复杂度:O(log2n)。

  假如有一组数为2,3,4,5,6,11,13,22,35要查给定的值5(x).可设三个变量start,mid,end分别指向数据的上界,中间和下界,mid=(start+end)/2。

  1.开始令start=0(指向2),end=8(指向35),则mid=4(指向6)。因为mid>x,故应在前半段中查找。

  2.令新的end=mid-1=3,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。

  3.令新的start=mid+1=2,而end=3不变,则新的mid=2,此时a[mid]

  例:在有序的有N个元素的数组中查找用户输进去的数据x。

  算法如下:

  1.确定查找范围start=0,end=N-1,计算中项:mid=(start+end)/2。 //N表示数组的长度

  2.若a[mid]=x或start>=end,则结束查找;否则,向下继续。

  3.若a[mid]

  若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。

  例:数组arr = { 2, 5, 11, 3, 22, 6, 13, 35, 4 };

  进行二分查找以前要对数组排序,调用Arrays.sort()方法,确保数组是有序的,才能使用二分查找。

  public class BinarySearch {

  /**

  * 二分查找

  * 简介: 在二分搜寻法中,从数列的中间开始搜寻,如果这个数小于我们所搜寻的数,由于数列已排序,则该数左边的数一定都小于要搜寻的对象,

  * 所以无需浪费时间在左边的数;如果搜寻的数大于所搜寻的对象,则右边的数无需再搜寻,直接搜寻左边的数。

  * @param arr 待查找数组

  * @num 待查找数

  */

  public static int binarySearch(int[] arr,int num){

  int start = 0;

  int end = arr.length-1;

  while(start <= end){

  int mid = (start + end)/2;

  if(num > arr[mid]){

  start = mid +1 ;

  }else if(num < arr[mid]){

  end = mid -1;

  }else{

  return mid;

  }

  }

  return -1 ;

  }

  /**

  * @param args

  */

  public static void main(String[] args) {

  // TODO Auto-generated method stub

  int[] arr = { 2, 5, 11, 3, 22, 6, 13, 35, 4 };

  //对数组进行排序 调用Arrays类的sort()方法

  Arrays.sort(arr);

  int find = binarySearch(arr,5);

  if (find != -1) {

  System.out.println("找到数值于索引:" + find);

  } else {

  System.out.println("找不到数值");

  }

  }

  }

  显示结果:数值5的索引:3