手机版
你好,游客 登录 注册
背景:
阅读新闻

二分查找之Java实现

[日期:2012-05-07] 来源:Linux社区  作者:Wentasy [字体: ]

环境:Notpad ++ 6.0 + JDK 6.0.24

问题:用Java实现二分查找算法

算法剖析:

二分查找是在一个有序表(数据是按其值由小到大或由大到小依次存放的,这里我们以值由小到大排列为例)中,每次都与中间的那个元素比较,若相等则查找成功;否则,调整查找范围,若中间那个元素的值小于待查值,则在表的后一半中查找;若中间那个元素的值大于待查值,则在表的前一半中查找;如此循环,每次只与一半中的一个元素比较,可使查找效率大大提高。

二分查找之Java实现

代码:

  1. import java.util.*;  
  2.   
  3. public class FindSearch{  
  4.   
  5.     public static void main(String [] args){  
  6.           
  7.           
  8.         int a[] = {247182534566889};  
  9.         System.out.println("打印原始数据:");  
  10.         for (int i = 0; i < a.length; ++ i){  
  11.             System.out.print(a[i] + " ");  
  12.         }  
  13.         System.out.println();  
  14.           
  15.         System.out.println("请输入要查找的整数:");  
  16.         Scanner scan = new Scanner(System.in);  
  17.         int num = scan.nextInt();  
  18.         int pos = 0;  
  19.         pos = binaryFind(a, num);  
  20.         if (-1 != pos)  
  21.             System.out.println("所查整数在数组中的位置下标是:" + pos);  
  22.         else  
  23.             System.out.println("没找到待查数据!");  
  24.     }  
  25.       
  26.     public static int binaryFind(int a[],int num){  
  27.       
  28.         int low, mid, high;  
  29.           
  30.         low = 0;//low是第一个数组元素的下标   
  31.         high = a.length - 1;//high是最后一个数组元素的下标   
  32.         mid = (low + high) / 2;//mid是中间那个数组元素的下标   
  33.           
  34.         while (low <= high){  
  35.           
  36.             if (num == a[mid]){  
  37.                 return  mid;  
  38.             }else if (num > a[mid]){  
  39.                 low = mid + 1;//要找的数可能在数组的后半部分中   
  40.                 mid = (low + high) / 2;  
  41.             }else{  
  42.                 high = mid - 1;//要找的数可能在数组的前半部分中   
  43.                 mid = (low + high) / 2;  
  44.             }  
  45.         }  
  46.           
  47.           
  48.         //mid是数组元素下标,若为-1则表示不存在要查的元素   
  49.         if (mid != ((low + high) / 2))  
  50.             return mid;  
  51.         else  
  52.             return -1;  
  53.               
  54.     }  
  55. }  

运行效果截图:

二分查找之Java实现

linux
相关资讯       Java教程 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款