梦想还是要有的，万一忘了咋办？

0%

二分查找

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

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

特点

  • 查找时间复杂度 O(logn) ，对数时间复杂度 速度惊人
  • 必须是有序数组
  • 数据量太小效果不明显
  • 数据量太大，由于数组是需要连续内存，系统剩余2G内存可能也无法提供连续的1G空间。

要领

  • 循环退出条件
    是 low>=high，而不是 low>high
  • mid 的取值，
    • (low+high)/2 很大时可能溢出
         - low+(high-low)/2
         - low+((high-low)>>1) ,位运算效率更高
  • low、high 的更新
    一定是low=mid+1，high=mid-1，写错会出现死循环

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low >= high) return -1;
  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

二分查找变体

第一个等于n的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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 if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

最后一个等于n的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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 if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

第一个大于等于n的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

最后一个小于等于n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int bsearch7(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 {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

应用

ip地址查询

基础数据：

1
2
3
4
5
6
7
8
9
10
10.1.1.1 - 11.2.1.1.1 北京
13.1.1.1 - 14.2.1.1.1 上海
....
//转换为int有序数组
n<=123456 北京
n<=789122 上海
[123456,789122]
//利用变体最优一个小于等于n，找到 123456 
//检查是否在 ip区间
//在的话返回位置信息