基础算法之二分查找

发布于   |   分类于   |     |   阅读次数

什么是二分查找

二分查找用于对已排序的数据进行快速查找，时间复杂度O(logn)。
最基本的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//c++实现二分查找_返回第一个找到的等于target的元素下标_找不到返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target < a[mid]){
            high = mid - 1;
        }else if(target > a[mid]){
            low = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

举几个例子

但是，通常需要根据具体问题进行一些变化，举几个具体问题为例。

I 搜索插入位置

该问题是在一个有序数组中插入一个元素，让你找到插入的下标, 可以认为要找的结果就是大于等于目标值的第一个元素的下标，并且当所有元素均小于目标值时返回最后一个元素的下一个下标。

II 实现int sqrt(int x), 返回x的平方根

该问题是要求最大的满足如下条件的数res：res * res <= x , 在二分查找问题中可以表述为平方小于等于目标值的最后一个数。

III 统计比给定整数小的数的个数

该问题可以表述为求小于目标值的最后一个数的下标+1。因此虽然二分法思路很简单，但是解决具体问题需要我们把握细节，否则功亏一篑。

二分查找变形

变形I:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c++实现二分查找_返回第一个等于target的元素的下标_找不到返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target <= a[mid]){
            high = mid - 1;
        }else if(target > a[mid]){
            low = mid + 1;
        }
    }
    if(low < n && a[low] == target){
        return low;
    }
    return -1;
}

变形II:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c++实现二分查找_返回最后一个等于target的元素的下标_找不到返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target < a[mid]){
            high = mid - 1;
        }else if(target >= a[mid]){
            low = mid + 1;
        }
    }
    if(high >= 0 && a[high] == target){
        return high;
    }
    return -1;
}

变形III:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c++实现二分查找_返回第一个大于等于target的元素的下标_都小于target返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target <= a[mid]){
            high = mid - 1;
        }else if(target > a[mid]){
            low = mid + 1;
        }
    }
    if(low < n){
        return low;
    }
    return -1;
}

变形IV:

1
2
3
4
5
6
7
8
9
10
11
12
13
//c++实现二分查找_返回最后一个小于等于target的元素的下标_都大于target返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target < a[mid]){
            high = mid - 1;
        }else if(target >= a[mid]){
            low = mid + 1;
        }
    }
    return high;
}

变形V:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c++实现二分查找_返回第一个大于target的元素的下标_都小于等于target返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target < a[mid]){
            high = mid - 1;
        }else if(target >= a[mid]){
            low = mid + 1;
        }
    }
    if(low < n){
        return low;
    }
    return -1;
}

变形VI:

1
2
3
4
5
6
7
8
9
10
11
12
13
//c++实现二分查找_返回最后一个小于target的元素的下标_都大于等于target返回-1
int binarySearch(int a[], int n, int target){
    int low = 0, high = n-1, mid;
    while(low <= high){
        mid = low + ((high-low)>>1);
        if(target <= a[mid]){
            high = mid - 1;
        }else if(target > a[mid]){
            low = mid + 1;
        }
    }
    return high;
}

总结

下面总结一下编写二分查找算法的关键点/易错点：
1 循环条件任何情况下都是low <= high, 不要漏掉等号
2 查找第一个满足某条件的数最后返回low或NOT_FOUND, 查找最后一个满足某条件的数最后返回high或NOT_FOUND,
3 条件为==时向左找还是向右找需要考虑清楚
4 最后可能需要对要返回的下标进行范围检查、对下标对应的数是否满足条件进行检查