各種二分查找

二分查找

給定一個有序（不降序）數組arr。

1、求任意一個i使得arr[i]等于val，不存在則傳回-1

2、求最小的i使得arr[i]等于val，不存在則傳回-1

3、求最大的i使得arr[i]等于val，不存在則傳回-1

4、求最大的i使得arr[i]小于val，不存在則傳回-1

5、求最小的i使得arr[i]大于val，不存在則傳回-1

一個錯誤的二分查找：

int bisearch(int *arr, int b, int e, int val)
{
    while(b<e)
    { 
        int mid = (b+e)>>2;
        if(arr[mid] <= val)
        {
            b = mid; 
        }
        else
        {
            e = mid-1; 
        } 
    }
    if(arr[e] == val)
    {
        return e; 
    } 
    else
    {
        return -1; 
    } 
}
           

下面通過建構測試用例來找出這個程式的問題

對于所有有效輸入

在arr數組中查找元素val,對于問題123建構如下的測試用例。

arr數組	找到	未找到
空集	不存在	1
1個元素	2	3
多個元素	arr中含有一個val   含有多個 位于arr開頭  4        5 結尾           6        7 中間           8        9	比最小的小            10 比最大的大            11 在範圍内就是不含有    12

建構測試用例

1	int a1[] = {}; cout << bisearch(a, 0, sizeof(a1)/sizeof(int)-1, 8) << endl;
2	int a2[] = {8}; cout << bisearch(a, 0, sizeof(a2)/sizeof(int)-1, 8) << endl;
3	int a3[] = {10}; cout << bisearch(a, 0, sizeof(a3)/sizeof(int)-1, 8) << endl;
4	int a4[] = {1,2,3,4,5,6,7,7,7,7,7}; cout << bisearch(a, 0, sizeof(a4)/sizeof(int)-1, 1) << endl;
5	int a5[] = {1,1,1,2,3,4,5,6,7,7,7,7,7}; cout << bisearch(a, 0, sizeof(a5)/sizeof(int)-1, 1) << endl;
6	int a6[] = {1,2,3,4,5,6,7,7,7,7,7,8}; cout << bisearch(a, 0, sizeof(a6)/sizeof(int)-1, 8) << endl;
7	int a7[] = {1,2,3,4,5,6,7,7,7,7,7,8,8,8,8}; cout << bisearch(a, 0, sizeof(a7)/sizeof(int)-1, 8) << endl;
8	int a8[] = {1,2,3,4,5,6,7,7,7,7,7,8,8,8,10,10,12}; cout << bisearch(a, 0, sizeof(a8)/sizeof(int)-1, 6) << endl;
9	int a9[] = {1,2,3,4,5,6,7,7,7,7,7,8,8,8,10,10,12}; cout << bisearch(a, 0, sizeof(a9)/sizeof(int)-1, 8) << endl;
10	int a10[] = {2,3,4,5,6,7,7,7,7,7}; cout << bisearch(a, 0, sizeof(a10)/sizeof(int)-1, 1) << endl;
11	int a11[] = {2,3,4,5,6,7,7,7,7,7}; cout << bisearch(a, 0, sizeof(a11)/sizeof(int)-1, 12) << endl;
12	int a12[] = {2,3,4,5,7,7,7,7,7}; cout << bisearch(a, 0, sizeof(a12)/sizeof(int)-1, 6) << endl;

期望的測試結果

測試用例編号	問題1	問題2	問題3
1	-1	-1	-1
2
3	-1	-1	-1
4
5	0-2任意	2
6	11	11	11
7	11-14任意	11	14
8	5	5	5
9	11-13	11	13
10	-1	-1	-1
11	-1	-1	-1
12	-1	-1	-1

對于上面那個錯誤程式：測試樣例4進入死循環，經過分析發現，（來自程式設計之美）

也就是說一種情況下沒有縮小範圍導緻。

對每一種情況都縮小範圍，可以得到題目1的如下代碼：可以通過全部測試樣例

//遞歸
int bisearch(int *arr, int s, int e, int val)
{
    if(s>e) return -1;
    int mid = s + ((e - s) >>1);
    if(arr[mid] == val) return mid;
    else if(arr[mid] < val) return bisearch(arr,mid+1, e, val);
    else return bisearch(arr,s, mid-1, val);
}
// 非遞歸
int bisearch(int *arr, int s, int e, int val)
{
    while(s<=e)
    {
        int mid = s + ((e-s)>>2);
        if(arr[mid]==val) return mid;
        else if(arr[mid]<val)  s=mid+1;
        else e=mid-1; 
    }
    return -1; 
}
//或者
int bisearch(int *arr, int s, int e, int val)
{
    /*
    循環結束有兩種情況
    s為偶數  s=e
    s為奇數  s=e-1 
    */ 
    while(s < e-1)
    {
        int mid = s+((e-s)>>1);
        if(arr[mid]<=val)
        {
            s=mid; 
        }else{
              // 不需要e=mid-1 防止s=e 
            e=mid; 
        } 
    } 
    if(arr[s]==val)  return s;
    if(arr[e]==val)  return e;
    return -1; 
}
           

//第二題：
int bisearch(int *arr, int s, int e, int val)
{
    while(s <= e)
    {
        if(arr[s]==val)  return s; 
        int mid = s+((e-s)>>1);
        if(arr[mid]<val)
        {
            s=mid+1; 
        }else if(arr[mid]==val){
            e=mid; 
        } else{
            e=mid-1; 
        } 
    } 
    return -1; 
}
//第三題：
int bisearch(int *arr, int s, int e, int val)
{
    while(s <= e)
    {
        if(arr[e]==val) return e;
        int mid=s+((e-s-1)>>2)+1; // 盡量往後落，也就是3和4落在4 2和6仍然也落在4 
        if(arr[mid] < val)
            s=mid+1;
        else if(arr[mid] == val) 
            s=mid;
        else 
            e=mid-1; 
    } 
    return -1; 
}
           

對于4,5問題不存在找不到的情況，建構測試用例

arr	val
空集	任意1
1個	相等2 大于3 小于 4
多個	小于最小5 等于最小 6 在中間相等7  不等8 等于最大 9 大于最大10

1	int a1[] = {}; cout << bisearch(a1, 0, sizeof(a1)/sizeof(int)-1, 8) << endl;
2	int a2[] = {8}; cout << bisearch(a2, 0, sizeof(a2)/sizeof(int)-1, 8) << endl;
3	int a3[] = {10}; cout << bisearch(a3, 0, sizeof(a3)/sizeof(int)-1, 8) << endl;
4	int a4[] = {5}; cout << bisearch(a4, 0, sizeof(a4)/sizeof(int)-1, 8) << endl;
5	int a5[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a5, 0, sizeof(a5)/sizeof(int)-1, 1) << endl;
6	int a6[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a6, 0, sizeof(a6)/sizeof(int)-1, 3) << endl;
7	int a7[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a7, 0, sizeof(a7)/sizeof(int)-1, 7) << endl;
8	int a8[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a8, 0, sizeof(a8)/sizeof(int)-1, 9) << endl;
9	int a9[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a9, 0, sizeof(a9)/sizeof(int)-1, 18) << endl;
10	int a10[] = {3,5,6,7,7,7,8,8,8,8,12,18}; cout << bisearch(a10, 0, sizeof(a10)/sizeof(int)-1, 20) << endl;

測試用例編号	問題4	問題5
1	-1	-1
2	-1	-1
3	-1
4	-1
5	-1
6	-1	1
7	2	6
8	9	10
9	10	-1
10	11	-1

//第四題
int bisearch(int *arr, int s, int e, int val)
{
    //求最大的i使得arr[i]小于val，不存在則傳回-1
    while(s<=e){
        if(arr[e]<val) return e; 
        int mid = s+((e-s-1)>>1)+1;
        if(arr[mid]<val){
            s=mid; 
        } 
        else{
             e=mid-1; 
        }            
    } 
    return -1; 
}
//第五題
int bisearch(int *arr, int s, int e, int val)
{
    //求最小的i使得arr[i]大于val，不存在則傳回-1
    while(s<=e){
        if(arr[s] > val) return s; 
        int mid = s + ((e-s)>>1); 
        if(arr[mid]<=val){
            s=mid+1; 
        } else{
            e=mid; 
        } 
    } 
    return -1; 
}