从线性搜索到二分搜索

发表于 更新于 分类于
学习笔记

Linear Search也就是brute force(暴力破解)

例: 求一个数的平方根

1
2
3
4
5
6
7
8
9
10
11
private int sqrt(int n) {
  int sqrt = 0;
  for (int i = 0; i <= n; i++) {
    if (i * i == n) {
      sqrt = i;
    }
  }
  return sqrt;
}
// 例:
sqrt(25)=5

如下图所示:

Binary Search(二分搜索)

套用上述案例

在0-25之间,
low:0, mid:12, high:25
1212=144>25
因此, 25的平方差会在a区内

在0和12之间,
low:0, mid:6: high:12
66=36>25,
因此, 25的平方差会在a区内

在0和6之间,
low:0, mid:3: high:6
33=9<25,
因此, 25的平方差会在b区内

在3和6之间,
low:3, mid:4: high:6
44=16<25,
因此, 25的平方差会在b区内,
省略最后一步, 最终结果为5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int sqrt(int n) {
  int low = 0;
  int high = n;
  int sqrt = 0;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (mid * mid == n) {
      sqrt = mid;
    }
    if (mid * mid > n) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return sqrt;
}