算法 —— 二分查找

青旅半醒 2022-05-30 06:22 275阅读 0赞

//二分查找
    int binarySearch(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key < arr[mid]) {//key在左边
                right = mid - 1;
            } else if (arr[mid] < key) {//key在右边
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

**转载自：https://www.cnblogs.com/bofengyu/p/6761389.html**

二分查找的变形

随着二分查找的进行，如果找到key并不结束循环的话，最终的结束状态会是right < left，并且right + 1 = left。

当数组中存在key时，根据二分区间选择的不同，这里又分为两种情况，如下图（key为2时），

当数组中不存在key时，最后仅有一种情况，即把图中的黄色框框去掉。

![638419-20170425120713569-1636091053.png][]

那么，可以找到

1 最后一个小于key的元素，1，

2 第一个大于等于key的元素，2，

3 最后一个小于等于key的元素，2，

4 第一个大于key的元素，5，

另外，如果存在多个key时，稍加判断，就可以找到

5 第一个与key相等的元素

6 最后一个与key相等的元素

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

//1 查找最后一个小于key的元素
    int findLastLess(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key <= arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

**2 查找第一个大于等于key的元素**

//2 查找第一个大于等于key的元素
    int findFirstGreaterEqual(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key <= arr[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }

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

//3 查找最后一个小于等于key的元素
    int findLastLessEqual(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

**4 查找第一个大于key的元素**

//4 查找第一个大于key的元素
    int findFirstGreater(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key < arr[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }

**5 查找第一个与key相等的元素**

//5 查找第一个与key相等的元素
    int findFirstEqual(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key <= arr[mid]) {
                right = mid - 1;
            } else {//arr[mid] < key
                left = mid + 1;
            }
        }
        //arr[right] < key <= arr[left]
        //right是最后一个小于key的
        //left是第一个大于等于key的
        if (left < len && arr[left] == key) {
            return left;
        }
        return -1;
    }

**6 查找最后一个与key相等的元素**

//6 查找最后一个与key相等的元素
    int findLastEqual(int arr[], int len, int key)
    {
        int left = 0;
        int right = len - 1;
        int mid;
    
        while (left <= right) {
            mid = (left + right) / 2;
            if (key < arr[mid]) {
                right = mid - 1;
            } else {//arr[mid] <= key
                left = mid + 1;
            }
        }
        //arr[right] <= key < arr[left]
        //right是最后一个小于等于key的
        //left是第一个大于key的
        if (right >= 0 && arr[right] == key) {
            return right;
        }
        return -1;
    }

[638419-20170425120713569-1636091053.png]: /images/20220530/3abe31fc98f54fc7b7c65e9750431b9d.png