二分查找,你真的掌握了吗?

  1. 前言
    1. 二分查找函数实现:
    2. 题目一
    3. 题目二
    4. 题目三
    5. 题目四
    6. 题目五
    7. 题目六
    8. 题目七
    9. 题目八
    10. 题目九
    11. 题目十
    12. 题目十一
    13. 题目十二
    14. 题目十三
  2. 结语

前言

二分查找,最基本的算法之一,也是面试中常被考察的重点,因为基本的算法最能反映出一个人的基础是否扎实。本文对二分查找相关题目做一个总结。

二分查找函数实现:

int bin_search(int arr[], int n, int key)
{
    int mid = 0;
    int low = 0, high = n-1;  
    while (low <= high)
    {
        mid = low + (high - low) >> 1;
        if (arr[mid] == key)
        {
            return mid;//找到返回下标
        }
        else if (arr[mid] < key)
        {
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
    return -1;//找不到返回-1
}

题目一

给定一个有序(非降序)数组A,求任意一个i使得A[i]等于key,不存在则返回-1

这个是最原始的二分查找题目,利用数组的有序特性,拆半查找,使得查找时间复杂度为O(logN)。请参考实现代码与注释。

int search(int arr[], int n, int key)  
{  
    int low = 0, high = n-1;  
    while(low <= high)  
    {  
        // 注意:若使用(low+high)/2求中间位置容易溢出  
        int mid = low+((high-low)>>1);   
        if(A[mid] == key)  
            return mid;  
        else if(A[mid] < key)  
            low = mid+1;  
        else // A[mid] > key  
            high = mid-1;  
    }  
    return -1;  
}  

题目二

给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于key,不存在则返回-1

此题也就是求key在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找,如果不存在直接返回-1,如果存在,然后再顺序找到这个等于key值区间的最左位置,这样的话,最坏情况下的复杂度就是O(n)了,没有完全发挥出二分查找的优势。这里的解法具体过程请参考实现代码与注释。

int searchFirstPos(int arr[], int n, int key)  
{  
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] < key)  
            low = mid+1;  
        else // A[mid] >= key  
            high = mid;  
    }  
    /*  
    循环过程中,当low大于0时,A[low-1]是小于key的,因为A[mid] < key时,
    low=mid+1;当high小于n-1时,A[high]是大于等于key的,因为A[mid] >= key时,
    high = mid;循环结束时,low 等于 high,所以,如果A[low](A[high])等于key,
    那么low(high)就是key出现的最小位置,否则key在数组中不存在。
    */  
    if(A[low] != key)  
        return -1;  
    else  
        return low;  
}  

题目三

给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于key,不存在则返回-1

此题也就是求key在数组中最后一次出现的位置。与上一题基本一样,但是有个地方要注意,具体请参考实现代码与注释。

int searchLastPos(int arr[], int n, int key)  
{     
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        /*
        这里中间位置的计算就不能用low+((high-low)>>1)了,因为当low+1等于high
        且A[low] <= key时,会死循环;所以这里要使用low+((high-low+1)>>1),
        这样能够保证循环会正常结束。
        */  
        int mid = low+((high-low+1)>>1);  
        if(A[mid] > key)  
            high = mid-1;  
        else // A[mid] <= key  
            low = mid;  
    }  
    /*  
    循环过程中,当high小于n-1时,A[high+1]是大于key的,因为A[mid] > key时,
    high=mid-1;当low大于0时,A[low]是小于等于key的,因为A[mid] <= key时,
    low = mid;循环结束时,low 等于 high,所以,如果A[high](A[low])等于key,
    那么high(low)就是key出现的最大位置,否则key在数组中不存在。
    */  
    if(A[high] != key)  
        return -1;  
    else  
        return high;  
}  

题目四

给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]小于key,不存在则返回-1

也就是求小于key的最大元素的位置。请参考实现代码与注释。

int searchLastPosLessThan(int arr[], int n, int key)  
{  
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low+1)>>1); // 注意,不要导致死循环  
        if(A[mid] < key)  
            low = mid;  
        else // A[mid] >= key  
            high = mid-1;  
    }  
    /*  
    循环过程中,当low大于0时,A[low]是小于key的,因为A[mid] < key时,
    low=mid;当high小于n-1时,A[high+1]是大于等于key的,因为A[mid] >= key时,
    high = mid-1;循环结束时,low 等于 high,所以,如果A[low](A[high])小于key,
    那么low(high)就是要找的位置,否则不存在这样的位置(A[0] >= key时)。
    */  
    return A[low] < key ? low : -1;  
}  

题目五

给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]大于key,不存在则返回-1。

也就是求大于key的最小元素的位置。请参考实现代码与注释。

int searchFirstPosGreaterThan(int arr[], int n, int key)  
{  
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] > key)  
            high = mid;  
        else // A[mid] <= key  
            low = mid+1;  
    }  
    /*  
    循环过程中,当low大于0时,A[low-1]是小于等于key的,因为A[mid] <= key时,
    low=mid+1;当high小于n-1时,A[high]是大于key的,因为A[mid] > key时,
    high = mid;循环结束时,low 等于 high,所以,如果A[high](A[low])大于key,
    那么high(low)就是要找的位置,否则不存在这样的位置(A[n-1] <= key时)。
    */  
    return A[high] > key ? high : -1;  
}  

题目六

给定一个有序(非降序)数组A,可含有重复元素,求key在数组中出现的次数

求出第一次出现位置和最后一次出现位置。由于前面都已实现,这里不多解释。请参考实现代码与注释

int count(int arr[], int n, int key)  
{  
    int firstPos = searchFirstPos(A, n, key); // 第一次出现位置  
    if(firstPos == -1)  
        return 0;  
    int lastPos = searchLastPos(A, n, key);  // 最后一次出现位置  
    return lastPos-firstPos+1;  // 出现次数  
}  

题目七

给定一个有序(非降序)数组A,若key在数组中出现,返回位置,若不存在,返回它应该插入的位置

如 [1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

int searchInsert(int arr[], int n, int key) {  
    // 如果比最大值还大,那插入位置就是位置n  
    if(A[n-1] < key)   
        return n;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] >= key)  
            high = mid;  
        else // A[mid] < key  
            low = mid+1;  
    }  
    /*   
    循环过程中,当low大于0时,A[low-1]是小于key的,因为A[mid] < key时,  
    low=mid+1;当high小于n-1时,A[high]是大于等于key的,因为A[mid] >= key时,  
    high = mid;循环结束时,low 等于 high,所以,如果A[low](A[high])等于key,  
    那么low(high)就是key出现的位置,否则low就是key在数组中应该插入的位置。  
    */  
    return high;  
}  

题目八

给定一个有序(非降序)数组A,可含有重复元素,求绝对值最小的元素的位置

找第一个大于等于0的位置,然后和前一个元素的绝对值比较,返回绝对值较小的元素的位置。请参考实现代码与注释

int searchMinAbs(int arr[], int n)  
{  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] < 0)  
            low = mid+1;  
        else // A[mid] >= 0  
            high = mid;  
    }  
    /* 循环结束时,如果low != n-1,A[low] >= 0,如果low>0,A[low-1] < 0 */  
    if(low > 0 && abs(A[low-1]) < abs(A[low]))  
        return low-1;  
    else  
        return low;  
}  

题目九

给定一个有序(非降序)数组A和一个有序(非降序)数组B,可含有重复元素,求两个数组合并结果中的第k(k>=0)个数字

这个题目出现了两个数组,有序的,不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找,时间复杂度最低为O(k),就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。

int findKthIn2SortedArrays(int arr[], int m, int B[], int n, int k)  
{  
    if(m <= 0) // 数组A中没有元素,直接在B中找第k个元素  
        return B[k];  
    if(n <= 0) // 数组B中没有元素,直接在A中找第k个元素  
        return A[k];  
    int i = (m-1)>>1; // 数组A的中间位置  
    int j = (n-1)>>1; // 数组B的中间位置  
    if(A[i] <= B[j])  // 数组A的中间元素小于等于数组B的中间元素  
    {  
        /*
        设x为数组A和数组B中小于B[j]的元素数目,则i+1+j+1小于等于x,
        因为A[i+1]到A[m-1]中还可能存在小于等于B[j]的元素;
        如果k小于i+1+j+1,那么要查找的第k个元素肯定小于等于B[j],
        因为x大于等于i+1+j+1;既然第k个元素小于等于B[j],那么只
        需要在A[0]~A[m-1]和B[0]~B[j]中查找第k个元素即可,递归调用下去。
        */  
        if(k < i+1+j+1)  
        {  
            if(j > 0)  
                return findKthIn2SortedArrays(A, m, B, j+1, k);  
            else // j == 0时特殊处理,防止死循环  
            {  
                if(k == 0)  
                    return min(A[0], B[0]);  
                if(k == m)  
                    return max(A[m-1], B[0]);  
                return A[k] < B[0] ? A[k] : max(A[k-1], B[0]);  
            }  
        }  
        /*
        设y为数组A和数组B中小于于等于A[i]的元素数目,则i+1+j+1大于等于y;
        如果k大于等于i+1+j+1,那么要查找到第k个元素肯定大于A[i],因为
        i+1+j+1大于等于y;既然第k个元素大于A[i],那么只需要在A[i+1]~A[m-1]
        和B[0]~B[n-1]中查找第k-i-1个元素,递归调用下去。
        */  
        else  
            return findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1);  
    }   
    // 如果数组A的中间元素大于数组B的中间元素,那么交换数组A和B,重新调用即可  
    else  
        return findKthIn2SortedArrays(B, n, A, m, k);  
}  

题目十

一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求key在变化后的数组中出现的位置,不存在则返回-1

如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2.
我们先比较中间元素是否是目标值,如果是返回位置。如果不是,我们就应该想办法将搜索区间减少一半。因为存在旋转变化,所以我们要多做一些判断。我们知道因为只有一次旋转变化,所以中间元素两边的子数组肯定有一个是有序的,那么我们可以判断key是不是在这个有序的子数组中,从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。

int searchInRotatedArray(int arr[], int n, int key)   
{  
    int low = 0, high = n-1;  
    while(low <= high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] == key)   
            return mid;  
        if(A[mid] >= A[low])   
        {  
            // low ~ mid 是升序的  
            if(key >= A[low] && key < A[mid])  
                high = mid-1;  
            else  
                low = mid+1;  
        }  
        else  
        {  
            // mid ~ high 是升序的  
            if(key > A[mid] && key <= A[high])  
                low = mid+1;  
            else  
                high = mid-1;  
        }  
    }  
    return -1;  
}  

**如果这样的数组中存在重复元素,还能使用二分吗?答案是不能。请看几个栗子:
[1, 2, 2, 2, 2], [2, 1, 2, 2, 2], [2, 2, 1, 2, 2], [2, 2, 2, 1, 2], [2, 2, 2, 2, 1]这些都是有第一个数组旋转一次变化来的,我们不能通过二分确定是否存在元素1. **

题目十一

一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求最小值所在位置

如果中间元素小于左端元素,则最小值在左半区间内(包含中间元素);如果中间元素大于右端元素,则最小值在右半区间内(包含中间元素)。请参考实现代码与注释。

int searchMinInRotatedArray(int arr[], int n)   
{  
    if(n == 1)  
        return 0;  
    int low = 0, high = n-1;  
    while(low < high-1) // 保证mid != low且mid != high  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] < A[low]) // 最小值在low~mid  
            high = mid;  
        else // A[mid] > A[low], // 最小值在mid和high之间  
            low = mid;  
    }  
    return A[low] < A[low+1] ? low : low+1;  
}  

题目十二

一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求第k(k > 0)小元素的位置

*我们可以利用上一题的解答,求出最小值所在位置后,便可以求出第k小元素。请参考实现代码与注释 *

int searchKthInRotatedArray(int arr[], int n, int k)   
{  
    int posMin = searchMinInRotatedArray(A, n);  
    return (posMin+k-1)%n;  
}  

题目十三

查找数组中第一个比k大的数的下标

当low和high都是非负数时,使用 mid = low + (high - low) / 2;这种形式可以避免溢出。
当low和high一个为负另一个为非负时,用mid = (low + high) / 2;这种形式可以避免溢出。


int searrrch_first_larger_k(int arr[], int length, int key)  
{  
    if (arr == nullptr || length <= 0 || arr[length - 1] <= key)  
        return -1;  
    int res = length - 1,low=0,high=length-1;  
    while (low <= high)
    {  

        int mid = low + (high - low) / 2;  
        if (arr[mid] > key)  
        {  
            res = mid;  
            high = mid - 1;  
        }  
        else// if (arr[mid] <= key)  
            low = mid + 1;  
    }  
    return res;  
}  

结语

二分查找是个普遍考查点,只要深入了解某几个点就可以对二分查找运用自如。


部分资料来源于网络,版权属其原著者所有,只供学习交流之用。如有侵犯您的权益,请联系【公众号:码农印象】删除,可在下方评论,亦可邮件至ysluckly.520@qq.com。互动交流时请遵守宽容、换位思考的原则。

×

喜欢就点赞,疼爱就打赏

(function(){ var bp = document.createElement('script'); bp.src = '//push.zhanzhang.baidu.com/push.js'; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();
休闲小游戏