Shen Huang's Blog
0%

二分法以及相关变种介绍

Posted on Edited on

介绍

本文主要介绍二分法相关变种。

找出第一个与key相等的元素

1
2
3
4
5
6
7
8
9
10
11
int searchFirstEqual(int *arr, int n, int key)
{
    int left = 0, right = n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] >= key) right = mid - 1;
        else if(arr[mid] < key) left = mid + 1;
    }
    if( left < n && arr[left] == key) return left;
    return -1;
}

找出最后一个与key相等的元素

1
2
3
4
5
6
7
8
9
10
11
int searchLastEqual(int *arr, int n, int key)
{
    int left = 0, right = n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] > key) right = mid - 1;
        else if(arr[mid] <= key) left = mid + 1; 
    }
    if( right>=0 && arr[right] == key) return right;
    return -1;
}

查找第一个等于或者大于Key的元素

1
2
3
4
5
6
7
8
9
10
int searchFirstEqualOrLarger(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] >= key) right = mid-1;
        else if (arr[mid] < key) left = mid+1;
    }
    return left;
}

查找第一个大于key的元素

1
2
3
4
5
6
7
8
9
10
int searchFirstLarger(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] > key) right = mid-1;
        else if (arr[mid] <= key) left = mid+1;
    }
    return left;
}

查找最后一个等于或者小于key的元素

1
2
3
4
5
6
7
8
9
10
int searchLastEqualOrSmaller(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) {
        int m = (left+right)/2;
        if(arr[m] > key) right = m-1;
        else if (arr[m] <= key) left = m+1;
    }
    return right;
}

查找最后一个小于key的元素

1
2
3
4
5
6
7
8
9
10
int searchLastSmaller(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] >= key) right = mid-1;
        else if (arr[mid] < key) left = mid+1;
    }
    return right;
}

参考

[1] : http://blog.chinaunix.net/uid-1844931-id-3337784.html
[2] : http://www.jianshu.com/p/77e5e0e509e0

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info