二分查找

算法思想

用于查找排序数组中的某一位位置

代码分析

1.函数定义

```

function findMinGreenIndex(array,len,target)

        l = -1,r = len;

        while l + 1 < r

                mid = (l+r)/2

                if isGreen(array,mid,target)

                        r = mid

                else

                        l = mid

        return r

判绿函数(可以通过修改判这个函数结果不同问题)

function isGreen(array,mid,target)

        return array[mid]>=target

```

细节

1.迭代的过程

整个二分的过程是一个不断迭代区间的过程,并且 红色游标 始终是红色,绿色游标指向的元素始终是绿色.迭代的过程就不是不断向 红绿边界 逼近的过程

2.迭代结束条件

红色游标和绿色游标刚好指向红绿边界,且区间长度为.所以当区间为2时,结束循环.

3.游标的初始值

红色游标的初始值为-1,绿色游标初始值为数组长度.这是因为如果恰好所有元素都是红色或者都是绿色,那么就会违背红色游标始终在红色,绿色游标始终在绿色的条件

4.中点位置

中点位置公式:mid = (l+r)/2

中点始终在[0,n)的区间范围内

5.死循环

不可能会发生,因为当区间长度为2时结束循环.当区间长度为3时,一定可以变成区间长度为2的情况,区间长度为4时也一定会变成2或3.