水準上的差異

前幾天課堂上教了使用recursive的 binary search (在有序區間)，於是，我照了自己的想法來寫一個簡單的function

---

bool BinarySearch(int* a, int left, int right,const int SearchValue){
    if(left==right){
        if(a[left]=SearchValue) return true;
        else return false;
    }
    else if(left        int pivot=(left+right)/2;

        if(a[pivot]==SearchValue) return true;
        else if(a[pivot]>SearchValue) BinarySearch(a,left,pivot,SearchValue);
        else    BinarySearch(a,pivot,right,SearchValue);
    }
    else ;
}

---

再來看看我參考STL源碼剖析的p.376 lower_bound function 的改良寫法

---

bool BinarySearch(int *a,int left,int right,int value){
    int len=right-left;
    while(len>0){
        int half = len >> 1;   /* half/=2 */
        int middle = left + half;

        if(a[middle]==value){
            left=middle;
            break;
        }
        else if(a[middle]< value){
            left = middle+1;
            len = len - half - 1;
        }
        else len = half;
    }

    if(a[left]==value) return true;
    else return false;
}

---

技巧可謂高下立判