程序员基本功系列3——二分查找

1、二分查找概念  

1.1、核心思想  

  二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

  二分查找的时间复杂度是 O(logn),当数据量较大时,O(logn) 往往优于常量时间复杂度 O(1),例如:2的32次方,大约是42亿也只需要32次查找,但是常量级可能是 O(1000)甚至更大。所以 O(logn)是一种很高效的算法实现。

1.2、二分查找的局限性

  • 针对的是线性表结构,简单说就是数组

    比如链表也不能使用二分查找,主要二分查找需要按照下标随机访问元素。

  • 针对的是有序数据

  • 不能数据量太大的数据

    因为二分查找针对有序数组,但是数组是连续的,对于内存的要求较高。

2、简单二分查找的实现

  简单二分查找可以通过递归和非递归两种方式实现。简单二分查找假设数组中没有重复元素。

2.1、非递归方式

private int bsearch(int[] nums,int value){
        int low = 0;
        int high = nums.length-1;
        //1、终止条件
        while (low <= high){
            //2、计算中间位置
            int mid = low + ((high-low) >> 1);
            if (nums[mid] == value){
                return mid;
            }
            //3、更新范围
            else if (nums[mid] > value){
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        return -1;
    }    

这里有几点注意的:

  1、终止条件

    终止条件是 low <= high,而不是low < high

  2、计算中间位置 mid

    经常会写 mid = (low+high) / 2,这么写不太严谨,因为如果 low 和 high 足够大的话相加可能会溢出,可以写成 mid = low + (high-low) / 2。更高效点就是上面那种写法,因为计算机处理位运算更快。

  3、范围更新

    更新范围时要更新到 mid 的下一位或上一位,high = mid-1 或 low = mid+1。不要写成 high = mid 或 low = mid,这样可能造成死循环。

2.2、递归方式

    private int recurBsearch(int[] nums,int value){
        return recur(nums,0,nums.length-1,value);
    }

    private int recur(int[] nums,int low,int high,int value){
        //终止条件
        if (low > high)return -1;
        //计算中间位置
        int mid = low + ((high-low) >> 1);
        if (nums[mid] == value){
            return mid;
        }else if (nums[mid] > value){
            return recur(nums,low,mid-1, value);
        }else {
            return recur(nums,mid+1,high,value);
        }
    }

3、二分查找的变形

  二分查找的变形有很多种,我们看几种比较经典的变形案例。

3.1、查找第一个值等于给定值的元素

  来举一个例子:从数组 a[10]{1,3,4,5,6,8,8,8,11,18} 中查找第一个等于8的位置。有些解题代码很简洁,但是很难理解:

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);
    if (a[mid] >= value) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  if (low < n && a[low]==value) return low;
  else return -1;
}

  这段代码的逻辑就很难理解,如果死记硬背的话过几天可能就忘了。

  

 

上一篇:一个简单的断点续传方法案例


下一篇:SpringMVC文件上传