A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© ZZBY 中级黑马   /  2015-9-12 01:02  /  385 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

折半查找也叫二分法查找,即对数组二分取中间值和key比较key如果大于中间值,那么key一定在大的那一半,再对这一半进行二分,如此下去
它的特点是很快速高效率
缺点是要求数组是有序的

面试的时候会考到一种相关题型,即让你把一个数插入到一个有序的数组中,并且保证数组还是有序的。

下面是折半查找代码
  1. /*
  2. 折半查找
  3. */
  4. class ArrayTest02
  5. {
  6.         public static void main(String[] args)
  7.         {
  8.                 /*
  9.                 int[] arr = {3,1,5,4,7,9};
  10.                 int index = getIndex(arr,7);
  11.                 System.out.println("index = "+index);
  12.                 */
  13.                 int[] arr = {2,4,7,9,11,35,56};
  14.                 int index = halfSearch_2(arr,5);
  15.                 System.out.println("index = "+index);
  16.         }


  17.         //折半查找:可以提高效率。
  18.         //前提条件:该数组是有序的从大到小或者从小到大。
  19.         public static int halfSearch(int[] arr, int key)
  20.         {
  21.                 int min,mid,max;
  22.                 min = 0;
  23.                 max = arr.length-1;
  24.                 mid = (min+max)/2;

  25.                 while(key!=arr[mid])
  26.                 {
  27.                         if (key>arr[mid])
  28.                                 min = mid+1;
  29.                         else if (key<arr[mid])
  30.                                 max = mid-1;
  31.                         if (max < min)
  32.                                 return -1;
  33.                         mid = (min + max)/2;
  34.                 }
  35.                 return mid;
  36.         }


  37.         //折半查找的第二种方式。
  38.         public static int halfSearch_2(int[] arr, int key)
  39.         {
  40.                 int min,mid,max;
  41.                 min = 0;
  42.                 max = arr.length-1;

  43.                 while (min <= max)
  44.                 {
  45.                         mid = (min + max)/2;

  46.                         if(key>arr[mid])
  47.                                 min = mid+1;
  48.                         else if(key<arr[mid])
  49.                                 max = mid-1;
  50.                         else
  51.                                 return mid;
  52.                 }
  53.                 return -1;
  54.         }


  55.         //定义一个遍历查找数组中任意元素的方法。
  56.         //获取key第一次出现在数组中的位置。
  57.         //如果返回值为-1,证明该key在数组中不存在。
  58.         public static int getIndex(int[] arr, int key)
  59.         {
  60.                 for (int x=0; x<arr.length; x++)
  61.                 {
  62.                         if (key == arr[x])
  63.                                 return x;
  64.                 }
  65.                 return -1;
  66.         }
  67. }
复制代码



2 个回复

倒序浏览
值得学习ing!
回复 使用道具 举报
写个快速查找算法试试
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马