微信号:bigdatalab

介绍:宽客俱乐部旗下美国大数据实验室,大数据研究应用.

如何写出正确的二分法以及分析

2016-06-15 07:33 大数据实验室

二分法在平时经常用到,除了查找某个key的下标以外,还有很多变形的形式。比如 STL 里的 lower_bound,upper_bound

总结一下注意点,有这么几个:

  • 数组是非递增还是非递减

  • 结束条件,即while (condition) 应当是 3. 求mid应当是偏向左还是右,即 mid = (left + right) » 1, 还是 mid = (left + right + 1) » 1

  • 如何得到循环不变式

  • while结束后是否需要判断一次条件

整理了下常见的几个问题如下:

  1. 查找值key的下标,如果不存在返回-1.

  2. 查找值key第一次出现的下标x,如果不存在返回-1.

  3. 查找值key最后一次出现的下标x,如果不存在返回-1.

  4. 查找刚好小于key的元素下标x,如果不存在返回-1.

  5. 查找刚好大于key的元素下标x,如果不存在返回-1,等价于std::upper_bound.

  6. 查找第一个>=key的下标,如果不存在返回-1,等价于std::lower_bound.

leetcode上也有很多类似的题目。例如:Search a 2D Matrix

二分查找,必须条件是有序数组,然后不断折半,几乎每次循环都可以降低一半左右的数据量。因此是O(lgN)的方法,要注意的是二分查找要能够退出,不能陷入死循环。

二分查找用到的一个重要定义就是循环不变式,顾名思义,就是在循环中不会改变这么一个性质。举个例子,插入排序,不断的循环到新的索引,但保持前面的排序性质不变。其实就是数学归纳法,具体的定义不用管,我们在第一个例子里看下。

1. 查找值为key的下标,如果不存在返回-1.

先看一下伪代码:


1

2

3

4

while left > 1

    if array[mid] > key:

        mid = right - 1

    else if array[mid]

这里面包含怎样的循环不变式呢?

如果中间值比key大,那么[mid, right]的值我们都可以忽略掉了,这些值都比key要大。

只要在[left, mid-1]里查找就是了。相反,如果中间值比key小,那么[left, mid]的值可以 忽略掉,这些值都比key要小,只要在[mid+1, right]里查找就可以了。如果相等,表示找到了, 可以直接返回。因此,循环不变式就是在每次循环里,我们都可以保证要找的index在我们新构造 的区间里。如果最后这个区间没有,那么就确实是没有

注意mid的求法,可能会int越界,但我们先不用考虑这个问题,要记住的是这点:

mid是偏向left的,即如果left=1,right=2,则mid=1。

参考代码:


1

2

3

4

5

6

7

int BS(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] > key)

            right = mid - 1;

        else if (vec[mid]

接着考虑一个复杂一点的问题

2. 查找值key第一次出现的下标x,如果不存在返回-1.

我们仍然考虑中间值与key的关系:
1. 如果array[mid] 2. 如果array[mid]>key,那么x一定在[left, mid-1]区间里。
3. 如果array[mid]≤key,那么不能推断任何关系。
比如对key=1,数组{0,1,1,2,3},{0,0,0,1,2},array[mid] = array[2] ≤ 1,但一个在左半区间,一个在右半区间。
4. 如果array[mid]≥key,那么x一定在[left, mid]区间里。

综合上面的结果,我们可以采用1,4即 循环过程中一直满足key在我们的区间里。

这里需要注意两个问题:

1. 循环能否退出,我们注意到4的区间改变里是令right = mid,如果left=right=mid时,循环是无法退出的。
换句话说,第一个问题我们始终在减小着区间,而在这个问题里,某种情况下区间是不会减小的!

2. 循环退出后的判断问题,再看下我们的条件1,4组合,只是使得我们最后的区间满足了≥key,是否=key,还需要再判断一次。

参考代码:


1

2

3

4

5

int BS_First(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid]

接下来的这个问题还有一个小小的坑,需要注意下:

3. 查找值key最后一次出现的下标x,如果不存在返回-1.

省去分析的过程,我们直接写下想到的循环不变式:
1. 如果array[mid]>key,那么x一定在[left, mid-1]区间里。
2. 如果array[mid]≤key, 那么x一定在[mid, right]区间里。

这里需要注意个问题:

在条件2里,实际上我们是令left=mid,但是如前面提到的,如果left=1,right=2,那么mid=left=1,同时又进入到条件2,left=mid=1,即使我们在while设定了left 仍然无法退出循环,解决的办法很简单:

mid = (left + right + 1) >> 1

向右偏向就可以了。

参考代码:


1

2

3

4

5

6

7

8

9

10

11

12

int BS_Last(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] > key)

            right = mid - 1;

        else

            left = mid;

    }

    

    if (vec[left] == key)

        return left;

 

    return -1;

}

接下来的题目都是类似的。

只贴下循环不变式和参考代码,如果你有别的心得,或者这篇文章有错误欢迎提出。

4. 查找刚好小于key的元素下标x,如果不存在返回-1.

  1. 如果array[mid]

  2. 如果array[mid]≥key,那么x在区间[left, mid-1]

参考代码:


1

2

3

4

5

int BS_Last_Less(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid]

5. 查找刚好大于key的元素下标x,如果不存在返回-1,等价于std::upper_bound.

  1. 如果array[mid]>key,那么x在区间[left, mid]

  2. 如果array[mid]≤key,那么x在区间[mid + 1, right]

参考代码:


1

2

3

4

5

6

7

8

9

10

11

12

int BS_First_Greater(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] > key)

            right = mid;

        else

            left = mid + 1;

    }

 

    if (vec[left] > key)

        return left;

 

    return -1;

}

6. 查找第一个>=key的下标,如果不存在返回-1,等价于std::lower_bound.

  1. 如果array[mid]

  2. 如果array[mid]≥key,那么x在区间[left, mid]

参考代码:


1

2

3

4

5

6

7

8

9

int BS_First_Greater_Or_Equal(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] = key)

        return left;

 

    return -1;

}

如果有什么疑问或者错误,欢迎指出。

量化对冲实战培训班(八期)登录广州,报名进行中!

上课地点:广州

培训时间:2016年7月8--9日 

咨询电话/微信:13061694649

最后附上完整的代码及测试:

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

4

typedef vector VecInt;

//print arry

void Print(const VecInt& vec)

{

    printf("INDEX: ");

    for (unsigned int i = 0; i > 1;

        if (vec[mid] > key)

            right = mid - 1;

        else if (vec[mid] > 1;

        if (vec[mid] > 1;

        if (vec[mid] > key)

            right = mid - 1;

        else

            left = mid;

    }

    

    if (vec[left] == key)

        return left;

 

    return -1;

}

 

//查找刚好小于key的元素下标x,如果不存在返回-1.

int BS_Last_Less(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] > 1;

        if (vec[mid] > key)

            right = mid;

        else

            left = mid + 1;

    }

 

    if (vec[left] > key)

        return left;

 

    return -1;

}

 

//查找第一个>=key的下标,如果不存在返回-1,等价于std::lower_bound.

int BS_First_Greater_Or_Equal(const VecInt& vec, int key)

{

    int left = 0, right = vec.size() - 1;

    while (left > 1;

        if (vec[mid] = key)

        return left;

 

    return -1;

}

 

int main()

{

    srand(time(NULL));

 

    int count = 20;

    const int N = 10;

    while (count--)

    {

        printf("================  TEST  ================n");

        VecInt vec;

        for (int i = 0; i ::iterator iter = upper_bound(vec.begin(), vec.end(), key);

        int index = iter == vec.end() ? -1 : iter - vec.begin();

        printf("%20s%10d%10d%10dn", "Find First > Key:", key, BS_First_Greater(vec, key), index);

        iter = lower_bound(vec.begin(), vec.end(), key);

        index = iter == vec.end() ? -1 : iter - vec.begin();

        printf("%20s%10d%10d%10dn", "Find First >= Key:", key, BS_First_Greater_Or_Equal(vec, key), index);

    }

 

    return 0;}


来源:算法与数学之美





不能错过的高级研修:大数据时代的量化投资!


  • 如何写一个赚钱的量化投资策略

  • 量化投资实战经验

  • 量化投资在股票市场的应用

  • 期货CTA


2016年6月25-26日     深圳   两天5800元


咨询电话/微信:13061694649



 
大数据实验室 更多文章 用户画像数据建模方法 李光斗:警方是如何利用大数据抓到王全安的 降楼价,新加坡居然靠的是无人驾驶! 小数法则和经验主义 什么性格的人适合 Quant 这个职位?能否描述一下 Quant 一天的生活是怎样的?
猜您喜欢 年过三十,开始码字 了解下依赖注入 提升UITableView性能-复杂页面的优化 存储设备综述 【第2章第152回】深入浅出ES6(十四):let和const