March 31, 2019 · 数据结构与算法 本文字数: 796 阅读时长:4 min 全站字数:361.8k

二分查找

  1. 二分查找的适用范围
  2. 二分查找代码模板
    1. 非递归版本
    2. 递归版本
  3. leetcode题目练习
    1. 暴力解法
    2. 先进行二分查找, 再顺序查找
    3. 两次二分查找

二分查找的适用范围

二分查找的数据必须是有序的, 而且是线性表, 即可以通过下标通过O(1)复杂度获取元素.
另外数据规模太小, 二分查找的优势不明显;数据规模太大, 由于需要连续内存空间, 也不适合
使用二分查找, 除非内存空间足够.

另外二分查找不适用于动态变化的数据集合, 该类问题使用二叉搜索树或者红黑树. 二分查找
最适用于的场景是范围查询, 这一点二叉搜索树和红黑树都很难做到.

二分查找代码模板

非递归版本

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

return -1;
}

递归版本

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 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);
}
}

leetcode题目练习

34. Find First and Last Position of Element in Sorted Array

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[] {-1, -1};
int i = -1;
while (++i < nums.length) {
if (nums[i] == target) {
ret[0] = i;
ret[1] = i;
while (++i < nums.length && nums[i] == target) {
ret[1]++;
}
return ret;
}
}
return ret;
}
}

时间复杂度O(n), 空间复杂度O(1).

先进行二分查找, 再顺序查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[] {-1, -1};
int hi = nums.length - 1, lo = 0;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if (nums[mid] == target) {
ret[0] = ret[1] = mid;
int i = mid - 1;
while (i >= 0 && nums[i] == target) {
ret[0]--;
i--;
}
i = mid + 1;
while (i < nums.length && nums[i] == target) {
ret[1]++;
i++;
}
return ret;
} else if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ret;
}
}

时间复杂度O(logn), 在最差情况下, 数组元素完全一样时,复杂度是O(n), 空间复杂度O(1).

两次二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[] {-1, -1};

// find leftmost
int lo = 0, len = nums.length, hi = len - 1;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if (nums[mid] < target) {
lo = mid + 1;
} else if (nums[mid] > target) {
hi = mid - 1;
} else {
if (mid == 0 || nums[mid - 1] != target) {
ret[0] = mid;
break;
} else {
hi = mid - 1;
}
}
}

if (ret[0] == -1) {
return ret;
}

// find rightmost
lo = ret[0];
hi = len - 1;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if (nums[mid] < target) {
lo = mid + 1;
} else if (nums[mid] > target) {
hi = mid - 1;
} else {
if (mid == nums.length - 1 || nums[mid + 1] != target) {
ret[1] = mid;
break;
} else {
lo = mid + 1;
}
}
}
return ret;
}
}

时间复杂度O(logn), 空间复杂度O(1).