如何快速定位出一个IP地址的归属地？——二分查找变体

• 查找第一个值等于给定值的元素
• 查找最后一个值等于给定值的元素
• 查找第一个大于等于给定值的元素
• 查找最后一个小于等于给定值的元素
• 查找循环有序数组中等于给定值的元素

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
#include "ListNode.h"
using namespace std;

// 二分查找具有O(logn)的时间复杂度，很强，但是只能用于数组的数据结构，像链表就不适合

// 二分查找非递归法
int binarySearch(int num[], int length, int key){
    if(length < 1)
        return -1;
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        // 以后尽量使用位运算，不直接用(low + high) / 2是为了防止加法溢出
        middle = low + ((high - low) >> 1);
        if(num[middle] == key)
            return middle;
        if(num[middle] > key)
            high = middle - 1;
        else if(num[middle] < key)
            low = middle + 1;
    }
    // 没找到则返回-1
    return -1;
}

// 二分查找递归方法
int binarySearchPlus(int num[], int low, int high, int key){
    if(low > high)
        return -1;
    int middle = low + ((high - low) >> 1);
    if(num[middle] == key)
        return middle;
    if(num[middle] > key)
        return binarySearchPlus(num, low, middle - 1, key);
    else
        return binarySearchPlus(num, middle + 1, high, key);
}

// 排序数组中第一次出现k的位置
int binarySearchFirst(vector<int> num, int k, int length){
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        middle = low + ((high - low) >> 1);
        if(num[middle] == k){
            if(middle > 0 && num[middle - 1] != k || middle == 0)
                return middle;
            else
                high = middle - 1;
        }
        else if(num[middle] > k)
            high = middle - 1;
        else
            low = middle + 1;
    }
    return -1;
}

// 最后一次出现k的位置
int binarySearchLast(vector<int> num, int k, int length){
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        middle = low + ((high - low) >> 1);
        if(num[middle] == k){
            if(middle < length - 1 && num[middle + 1] != k || middle == length - 1)
                return middle;
            else
                low = middle + 1;
        }
        else if(num[middle] > k)
            high = middle - 1;
        else
            low = middle + 1;
    }
    return -1;
}

// 查找第一个大于等于给定值的元素（和大于不一样），妙啊
int binarySearchFirstHighPlus(int num[], int length, int key){
    if(length < 1)
        return -1;
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        middle = low + ((high - low) >> 1);
        if(num[middle] >= key){
            // 妙啊
            if(middle == 0 || num[middle - 1] < key)
                return middle;
            else
                // 往左走
                high = middle - 1;
        }
        else
            low = middle + 1;
    }
    return -1;
}

// 查找第一个小于等于给定值的元素（和小于不一样），妙啊
int binarySearchFirstLowPlus(int num[], int length, int key){
    if(length < 1)
        return -1;
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        middle = low + ((high - low) >> 1);
        if(num[middle] <= key){
            if(middle == length - 1 || num[middle + 1] > key)
                return middle;
            else
                // 往右走
                low = middle + 1;
        }
        else
            high = middle - 1;
    }
    return -1;
}

// 在循环有序数组中利用二分查找元素
// 如果加大点儿难度，比如在循环有序数组中查找第一个等于某值的元素，比如在{3,4,5,6,1,2,3,4,5}中查找4
int bsearchInCycleSortArray(int num[], int length, int key){
    if(length < 1)
        return -1;
    int low = 0;
    int high = length - 1;
    int middle = 0;
    while(low <= high){
        middle = low + ((high - low) >> 1);
        if(num[middle] == key)
            return middle;
        // 如果中间元素小于尾元素，说明右端是有序的，左端是循环的
        if(num[middle] < num[high]){
            // 如果目标元素在有序数组范围中，则后面的都是二分查找
            if(num[middle] < key && key <= num[high])
                low = middle + 1;
            // 如果不在，则在另一半继续查找
            else
                high = middle - 1;
        }
        // 如果中间元素大于尾元素，说明左端是有序的，右端是循环的
        else{
            // 如果目标元素在有序数组范围中，则后面的都是二分查找
            if(num[low] <= key && key < num[middle])
                high = middle - 1;
            // 如果不在，则在另一半继续查找
            else
                low = middle + 1;
        }
    }
    return -1;
}

int main(int argc, char* argv[]){

    int arr[6] = {4,5,6,1,2,3};

    cout<<bsearchInCycleSortArray(arr, 6, 2)<<endl;
    return 0;
}