黑马程序员技术交流社区

标题: 折半查找法，数组基本操作之一 [打印本页]
作者: ZZBY    时间: 2015-9-12 01:02
标题: 折半查找法，数组基本操作之一
折半查找也叫二分法查找，即对数组二分取中间值和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.         }


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

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


  42.         //折半查找的第二种方式。
  43.         public static int halfSearch_2(int[] arr, int key)
  44.         {
  45.                 int min,mid,max;
  46.                 min = 0;
  47.                 max = arr.length-1;

  49.                 while (min <= max)
  50.                 {
  51.                         mid = (min + max)/2;

  53.                         if(key>arr[mid])
  54.                                 min = mid+1;
  55.                         else if(key<arr[mid])
  56.                                 max = mid-1;
  57.                         else
  58.                                 return mid;
  59.                 }
  60.                 return -1;
  61.         }


  64.         //定义一个遍历查找数组中任意元素的方法。
  65.         //获取key第一次出现在数组中的位置。
  66.         //如果返回值为-1，证明该key在数组中不存在。
  67.         public static int getIndex(int[] arr, int key)
  68.         {
  69.                 for (int x=0; x<arr.length; x++)
  70.                 {
  71.                         if (key == arr[x])
  72.                                 return x;
  73.                 }
  74.                 return -1;
  75.         }
  76. }
复制代码



作者: 许庭洲    时间: 2015-9-14 22:37
值得学习ing!
作者: 王志志志    时间: 2015-9-14 22:52
写个快速查找算法试试



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2