查找算法——二分查找

看二分查找前,我们先看一下普通的查找,即线性查找。

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

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

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

 

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

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

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

最差的情况下,while 执行的次数为 O(logn) 次,循环体内执行一次用时 O(1),所以时间复杂度为 O(logn)。

  • 微信
  • 赶快加我聊天吧
  • weinxin
  • 博客交流群
  • 海纳百川,大家来水
  • weinxin
言曌

发表评论

:?::razz::sad::evil::!::smile::oops::grin::eek::shock::???::cool::lol::mad::twisted::roll::wink::idea::arrow::neutral::cry::mrgreen: