Fork me on GitHub

二分查找

发表于 | 分类于 | 次阅读
字数统计: 697 | 阅读时长 ≈ 3

基本代码

写法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int B_search(const vector<int> &v , int target){
    int l = 0 , r = v.size();
    while(l < r){
        int mid = (l + r) / 2;
        if(v[mid] > target){
            r = mid;
        }
        else if(v[mid] < target){
            l = mid + 1;
        }
        else return mid;
    }
    return -1;
}

写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int B_search(const vector<int> &v , int target){
    int l = 0 , r = v.size() - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(v[mid] > target){
            r = mid - 1;
        }
        else if(v[mid] < target){
            l = mid + 1;
        }
        else return mid;
    }
    return -1;
}

查找 <= target 的最大位置

  • 当target在序列中时，返回序列中最后出现target的位置
  • 当target不在序列中，但是在序列的范围内时，返回比target的最大位置
  • 当target比序列中任何元素都小时，返回-1
  • 当target比序列中任何元素都大师，返回最后一个元素的位置

写法1

1
2
3
4
5
6
7
8
9
10
11
int right_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size();
    while(l < r){
        int mid = (l + r) / 2;
        if(v[mid] > target){
            r = mid;
        }
        else l = mid + 1;
    }
    return l - 1;   // l 实际上指向的是大于target的最小位置
}

写法2

1
2
3
4
5
6
7
8
9
10
11
int right_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size() - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(v[mid] > target){
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return l - 1;
}

查找 < target 的个数

其实也可以用来求< target的最小位置

写法1

1
2
3
4
5
6
7
8
9
10
11
int left_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size();
    while(l < r){
        int mid = (l + r) / 2;
        if(v[mid] < target){
            l = mid + 1;
        }
        else r = mid;
    }
    return r;  // 如果要返回< target的最小位置，则是 return r-1;
}

写法2

1
2
3
4
5
6
7
8
9
10
11
int left_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size() - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(v[mid] < target){
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return l;  // 如果要返回< target的最小位置，则是 return r;
}

查找 < target 的最大位置，==target的最小位置

  • 当target在序列中时，返回序列中第一次出现target的位置
  • 当target不在序列中，但是在序列的范围内时，返回比target的最大位置
  • 当target比序列中任何元素都小时，返回-1
  • 当target比序列中任何元素都大时，返回最后一个元素的位置

写法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size();
    while(l < r){
        int mid = (l + r) / 2;
        if(v[mid] < target){
            l = mid + 1;
        }
        else r = mid;
    }
    if(v[l] == target){
        return l;
    }
    else return l-1;
}

写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left_bound(const vector<int> &v , int target){
    int l = 0 , r = v.size() - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(v[mid] < target){
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(v[l] == target){
        return l;
    }
    else return r;
}