二分查找有这么简单?

布满荆棘的人生 2022-05-19 02:53 123阅读 0赞

### 题目一 ###

> 给定一个有序（非降序）数组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;  
    }