查找算法——二分查找

avatar 2017年10月11日09:54:53 4 3176 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
看二分查找前，我们先看一下普通的查找，即线性查找。

一、线性查找，时间复杂度 O(n)

  1. package algorithm;
  3. public class Search_linear {
  4.     int Search(int [] arr, int x) {
  5.         for(int i=0;i<arr.length;i++) {
  6.             if(arr[i]==x)
  7.                 return i;//找到了，返回下标
  8.         }
  9.         return -1;//如果没找到，返回-1
  10.     }
  12.     public static void main(String args[]) {
  13.         int[] arr = {1,2,4,6,8};
  14.         Search_linear s = new Search_linear();
  15.         int x = s.Search(arr,4);
  16.         System.out.println(x); //2
  17.     }
  18. }

该算法的时间复杂度为 O(n) ，即线性的。我们能不能把时间复杂度再降低，提高效率呢？显示是可以的。


二、二分查找，时间复杂度 O(logn)

  1. package algorithm;
  3. public class Search_binary {
  4.     int Search(int[] arr, int x) {
  5.         int left = 0,right = arr.length-1;
  6.         int mid;
  7.         while(left<=right) {
  8.             mid = (left+right)/2;
  9.             if(x>arr[mid])
  10.                 left = mid+1;
  11.             else if(x<arr[mid])
  12.                 right = mid-1;
  13.             else
  14.                 return mid;
  15.         }
  16.         return -1;//没找到,返回-1
  17.     }
  19.     public static void main(String args[]) {
  20.         int[] arr = {1,2,4,6,8};
  21.         Search_binary s = new Search_binary();
  22.         int x = s.Search(arr,4);
  23.         System.out.println(x);//2
  24.     }
  25. }

我们发现，while 每执行一次，我们的查找范围就会缩减一半，也就是说：

最差的情况下，while 执行的次数为 O(logn) 次，循环体内执行一次用时 O(1),所以时间复杂度为 O(logn)。
历史上的今天
十月
11日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0