Catalog
  1. 1. 二分查找
    1. 1.1. 大O表示法
    2. 1.2. 简明代码
    3. 1.3. 注意问题
    4. 1.4. 例题
      1. 1.4.1. 方程求解(POJ 4140)
      2. 1.4.2. 在线翻译(POJ 2530)
二分查找

二分查找

比如你要查一个以P打头的通讯录用户,或者R开头的单词,都更适合从中间查找,这种算法就是二分查找。其输入是一个有序的元素列表,查找元素包含在列表中,返回该位置,否则返回null。
如果列表包含100个元素,简单查找最多需要100次,二分查找最多只需要7次;如果列表包含40亿个数字,二分查找最多只需要32次,即运行时间为对数时间(log时间)

大O表示法

指出了算法的速度
一些常见的大O运行时间:

  • O(log n),也叫对数时间,这样的算法包括二分查找。
  • O(n),也叫线性时间,这样的算法包括简单查找。
  • O(n * log n),这样的算法包括快速排序。
  • O(n²),选择排序,速度较慢。
  • O(n!),例如旅行商问题。

    简明代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int BinarySearch(int len[],int target,int low,int high)
    while(low <= high){
    int mid = low + (high-low) / 2;
    if (target == len[mid]){
    return mid;
    else if (target < len[mid])
    high = mid - 1;
    else
    low = mid + 1;
    }
    return null;
    }

二分法思想简单,数据量大时算法加速提升速度快,要求待查数据已被整理为有序列表。

注意问题

  1. 数据范围:整型范围为-2³¹~2³¹-1,二分查找时如果使用
    int mid = (high + low) / 2;
    对于较大的low和high可能相加后超过范围,因此使用
    int mid = low + (high-low) / 2;
  2. 边界确定。
    边界确定关系到二分查找算法的赋值与判断。如high > low还是high >= lowhigh = mid还是 high = mid - 1
    还有high的初值是n还是n-1(n指元素个数),一旦错误,会导致死循环或者返回错误的情况,应该保持统一的开闭区间,比如high初值为n时,是左闭右开区间[low,high),取子序列也应该是左闭右开区间,while( low< high),以及high = mid;,子区间序列为[low,mid),当high初始值为n-1,则与示例代码相同,子区间为[low,mid-1]。
    3.二分查找的变形,现实问题大多是二分查找的变形,不会是简单的基础模型,例如查找重复出现的元素第一次/最后一次出现的位置,返回小于(大于)或等于目标元素的最大(小)元素等,针对不同问题修改相应的判断和赋值语句,需要注意以下几点:
    • 注意high和low的赋值,保证目标元素必然不在排除序列中。
    • 每次二分过程注意low和high的赋值和循环条件判断,保证不会出现死循环,即要么排除元素序列减少,要么结束循环。
    • 退出循环时,分析此时目标元素形态,确定返回位置的正确表达形式。

      例题

      方程求解(POJ 4140)

      问题描述
      求下面方程的根:f(x) = x³- 5x²+ 10x - 80 = 0。
      输出要求
      精确到小数点后9位。
      输出样例
      5.705085930
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <math.h>
double BinarySearch(double low, double high) {
double mid;
double f;
while (high - low > 0.00000000001) //精度
{
mid = low + (high - low) / 2;
f = mid * mid * mid - 5 * mid * mid + 10 * mid - 80;
if (f < 0)
low = mid;
else
high = mid;
}
return mid;
}
int main(){
printf("%.9lf\n",BinarySearch(0.0,10.0));
return 0;
}

在线翻译(POJ 2530)

问题描述
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
输入
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.
输出要求
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as “eh”.
样例输入
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
样例输出
cat
eh
loops

思路
由于查找量大,最多可能有100000个,故采用二分法查找词条,这里要注意的是查找的内容为字符串,定义cmp()函数进行排序(sort函数的排序规则),字符串大小比较要用到strcmp()函数,strcmp(a,b)返回小于0的值表示a<b。
还要注意输入格式的问题,即如何准确发现空行,可以使用cin.peek()探查输入流的下一个字符。若为换行,结束输入,转入翻译阶段,同时使用cin.peek()前要使用cin.get()处理掉行末换行符,同时排序部分用到了algorithm标准函数库里的sort函数,从网上了解到,sort函数使用的排序方法是类似于快排的方法,时间复杂度为n*log2(n),执行效率较高!有关sort函数的用法,我参考了这篇文章sort函数有三个参数:(1)第一个是要排序的数组的起始地址。(2)第二个是结束的地址(最后一位要排序的地址)(3)第三个参数是排序的方法,可以是从大到小也可是从小到大,还可以不写第三个参数,此时默认的排序方法是从小到大排序。
Sort函数使用模板:Sort(start,end,排序方法)

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
struct Entry {
char english[11];
char foreign[11];
}entries[100005];
int Cmp(Entry entry1,Entry entry2) {
return strcmp(entry1.foreign, entry2.foreign) < 0; //将字典里的foreign从小到大排列
}

int main()
{
int num = 0;
char target[11];
while (true)
{
scanf("%s%s", entries[num].english,entries[num].foreign);
num++;
cin.get();
if (cin.peek() == '\n')break;
}
sort(entries, entries + num, Cmp);
while (scanf("%s",target) != EOF)
{
int low = 0;
int n = 0;
int high = num;
while (low < high)
{
int mid = low + (high + low) / 2;
n = strcmp(entries[mid].foreign, target);
if (n < 0)
low = mid;
else if (n > 0)
high = mid;
else {
printf("%s\n", entries[mid].english);
break;
}
}
if(n)printf("en\n");
}
return 0;
}

Author: Bbxren
Link: http://bbxren.site/2020/01/20/算法/二分法/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment