黑马程序员技术交流社区

标题: 练习二分查找法，查找数组中的某一个元素，返回索引值 [打印本页]
作者: 夜空中最亮的星    时间: 2015-6-27 22:29
标题: 练习二分查找法，查找数组中的某一个元素，返回索引值
二分查找算法是在有序数组中用到的较为频繁的一种算法，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
    1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找，
    2.寻找{6， 7， 8， 9}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
  1. class  IndexSearch{
  2.         public static void main(String[] args) {

  4.                 int[] arr = {1,2,3,4,5,6,7,8,9};
  5.                 int key = 9;

  7.                 int index = binarySearch(arr,key);

  9.                 System.out.println(key+"在数组中的索引值为："+index);
  10.         }

  12.                 //演示二分查找法,对于有序数组
  13.         public static int binarySearch(int[] arr,int key){
  14.                 //需要定义三个变量，用于记录住角标的变化。
  15.                 int min,max,mid;
  16.                 min = 0;
  17.                 max = arr.length-1;
  18.                 //只要min和max之间有距离，就有了折半的可能，而且有可能折半多次，使用while循环。。
  19.                 while(min<=max){
  20.                 //获取中间角标。
  21.                 mid = (max+min)/2;    //mid = (max+min)>>1;
  22.                 //获取中间角标上的元素和key进行比较。
  23.                 //来确定min和max的新值。或者叫做，确定新的查找范围。
  24.                 if(key>arr[mid])
  25.                         min = mid + 1;
  26.                 else if(key<arr[mid])
  27.                         max = mid - 1;
  28.                 else
  29.                         return mid;
  30.                 }
  31.                 return -1;
  32.         }
  33. }
复制代码



作者: 空城dream    时间: 2015-6-27 22:34
我还没学。。看看
作者: 进军黑马    时间: 2015-6-27 23:29
   分析的很细，注释明了。学习了



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