算法-搜索算法：二分查找（Binary Search）【前置条件：待查数据集必须是有序结构，可以右重复元素】【时间复杂度：O(logn)】

曾经终败给现在 2023-10-05 06:18 5阅读 0赞

**搜索**：是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。 搜索的几种常见方法：顺序/线性查找、二分法查找、二叉树查找、哈希查找

**二分查找**又称折半查找，优点是比较次数少，查找速度快，平均性能好；缺点是要求待查表：

*  必须采用顺序存储结构；
 *  必须按关键字大小有序排列；
 *  插入删除困难；

**二分查找/折半查找**方法适用于不经常变动而查找频繁的有序列表：

*  首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
 *  否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
 *  重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

**二分查找/折半查找**的时间复杂度：O(logn)【不考虑排序的时间】

*  最差时间复杂度: O(logn)；
 *  最优时间复杂度: O(1)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

很多时候，和二分查找法相关的算法问题，不是在数组中查找特定值，而是使用二分查找法搜索问题的解。

## 一、二分法查找指定数值 ##

### 1、递归方法 ###

java版本：

public class BinarySearch {
        
        /**
         * 二分查找的时间复杂度是O(log(n))
         * 1.二分查找依赖顺序表结构即数组
         * 2.二分查找针对的是有序数据
         * 3.递归方法
         */
        public static int search(int[] arr, int target) {
        
            return search(arr, 0, arr.length - 1, target);
        }
    
        private static int search(int[] arr, int left, int right, int target) {
        
            if (left > right)
                return -1;
            int mid = left + (right - left) / 2;
    
            System.out.println("target = " + target + "; arr[mid] = " + arr[mid] + "; mid = " + mid);
    
            if (arr[mid] == target) {
        
                return mid;
            }
            if (target < arr[mid]) {
        
                return search(arr, left, mid - 1, target);
            } else {
        
                return search(arr, mid + 1, right, target);
            }
        }
    
        public static void main(String[] args) {
        
            int arr[] = {
        3, 5, 11, 17, 21, 23, 101};
            int result = search(arr, 23);
            System.out.println("result = " + result);
        }
    }

输出结果：

target = 23; arr[mid] = 17; mid = 3
    target = 23; arr[mid] = 23; mid = 5
    result = 5

python版本：

def binary_search(alist, item):
        """二分查找,递归"""
        n = len(alist)
        if n > 0:
            mid = n // 2
            if alist[mid] == item:
                return True
            elif item < alist[mid]:
                return binary_search(alist[:mid], item)
            else:
                return binary_search(alist[mid + 1:], item)
        return False
    
    if __name__ == "__main__":
        li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
        print(binary_search(li, 55))
        print(binary_search(li, 100))

#### 2、非递归方法 ####

C++版本：

#include <iostream>
    
    int binary_search(int arr[], int left, int right, int target) {
        
        while (left <= right) {
        
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
        
                return mid;
            } else if (arr[mid] > target) {
        
                right = mid - 1;
            } else {
        
                left = mid + 1;
            }
        }
    }
    
    int main() {
        
        int arr[] = {
        3, 5, 11, 17, 21, 23, 101};
        int len = sizeof(arr) / sizeof(arr[0]);
        int target = 23;
        int result = binary_search(arr, 0, len - 1, target);
        std::cout << "result = " << result << std::endl;
    }

java版本：

public class BinarySearch02 {
        
        /**
         * 二分查找的时间复杂度是O(log(n))
         * 1.二分查找依赖顺序表结构即数组
         * 2.二分查找针对的是有序数据
         * 3.非递归方法
         */
        public static int search(int[] arr, int target) {
        
            int left = 0;
            int right = arr.length - 1;
            // 循环不变量：在arr[left, right]的范围中查找 target
            while (left < right) {
        
                int mid = left + (right - left) / 2;
                System.out.println("target = " + target + "; arr[mid] = " + arr[mid] + "; mid = " + mid);
                if (arr[mid] == target) {
        
                    return mid;
                }
                // 如果没找到目标值，则修改左右边界
                if (arr[mid] < target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return -1;
        }
    
    
        public static void main(String[] args) {
        
            int arr[] = {
        3, 5, 11, 17, 21, 23, 101};
            int result = search(arr, 23);
            System.out.println("result = " + result);
        }
    }

输出结果：

target = 23; arr[mid] = 17; mid = 3
    target = 23; arr[mid] = 23; mid = 5
    result = 5
    
    Process finished with exit code 0

python代码：方法一【循环不变量：在  n u m s \[ l e f t , r i g h t \] nums\[left, right\] nums\[left,right\] **左闭右闭** 区间查找target；初始范围是： n u m s \[ 0 , l e n ( n u m s ) − 1 \] nums\[0, len(nums) - 1\] nums\[0,len(nums)−1\]】

class Solution:
        """二分查找， 非递归"""
    
        def upper(self, nums, target):
            # 初始化查找范围
            left, right = 0, len(nums) - 1
    
            # 循环不变量：在nums[left, right]左闭右闭区间查找target
            # 如果left<=right，说明要搜索的数组中还存在要搜索的元素，该元素有可能是我们要找的元素，需继续搜索
            while left <= right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找target
                else:
                    left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找target
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return -1
    
    
    solution = Solution()
    nums = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    target = 54
    result = solution.upper(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = 0---right = 8
    本轮循环结束：left = 5---right = 8
    
    left = 5---right = 8
    
    最终：result =  6

python代码：方法二【循环不变量：在  n u m s \[ l e f t , r i g h t ) nums\[left, right) nums\[left,right) **左闭右开** 区间查找target；初始范围是： n u m s \[ 0 , l e n ( n u m s ) ) nums\[0, len(nums)) nums\[0,len(nums))】

class Solution:
        """二分查找， 非递归"""
    
        def upper(self, nums, target):
            # 初始化查找范围
            left, right = 0, len(nums)
    
            # 循环不变量：在nums[left, right)左闭右开区间查找target
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid  # 继续在nums[left, mid) 范围内寻找target
                else:
                    left = mid + 1  # 继续在nums[mid + 1, right) 范围内寻找target
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return -1
    
    
    solution = Solution()
    nums = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    target = 54
    result = solution.upper(nums, target)
    print("\n最终：result = ", result)

打印：

left = 0---right = 9
    本轮循环结束：left = 5---right = 9
    
    left = 5---right = 9
    本轮循环结束：left = 5---right = 7
    
    left = 5---right = 7
    本轮循环结束：left = 5---right = 6
    
    left = 5---right = 6
    
    最终：result =  5

## 二、二分法查找法变种 ##

### 1、upper：查找大于target的最小值 ###

【循环不变量：在  n u m s \[ l e f t , r i g h t \] nums\[left, right\] nums\[left,right\] **左闭右闭** 区间查找target；初始范围是： n u m s \[ 0 , l e n ( n u m s ) \] nums\[0, len(nums)\] nums\[0,len(nums)\]】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]

#### 1.1 C++版本 ####

#include <iostream>
    
    // 二分查找法：查找大于target的最小值
    
    int upper(int arr[], int left, int right, int target) {
        
        while (left < right) {
        
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
        
                left = mid + 1;
            } else if (arr[mid] < target) {
        
                left = mid + 1;
            } else {
        
                right = mid;
            }
        }
        return left;
    }
    
    int main() {
        
        int arr[] = {
        3, 5, 11, 17, 21, 23, 101, 101};
        int len = sizeof(arr) / sizeof(arr[0]);
        int target = 101;
        int result = upper(arr, 0, len, target);
        std::cout << "result = " << result << std::endl;
    }

#### 1.2 python版本： ####

class Solution:
        """二分查找法：查找大于target的最小值"""
    
        def upper(self, nums, target):
            # 初始化查找范围
            left, right = 0, len(nums)
    
            # 循环不变量：在nums[left, right]左闭右开区间查找大于target的最小值
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找目标值【由于nums[mid] == target，所以mid处的元素绝不可能是要找的值，排除掉】
                elif nums[mid] < target:
                    left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找目标值【由于nums[mid] < target，所以mid处的元素绝不可能是要找的值，排除掉】
                else:   # nums[mid] > target
                    right = mid  # 继续在nums[left, mid] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return left

比如：查找大于60的最小值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.upper(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = 0---right = 8
    本轮循环结束：left = 0---right = 4
    
    left = 0---right = 4
    本轮循环结束：left = 3---right = 4
    
    left = 3---right = 4
    本轮循环结束：left = 3---right = 3
    
    
    最终：result =  3

比如：查找大于99的最小值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 99
    result = solution.upper(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = 0---right = 8
    本轮循环结束：left = 5---right = 8
    
    left = 5---right = 8
    本轮循环结束：left = 7---right = 8
    
    left = 7---right = 8
    本轮循环结束：left = 8---right = 8
    
    
    最终：result =  8

比如：查找大于100的最小值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 100
    result = solution.upper(nums, target)
    print("\n最终：result = ", result)

打印结果：

#### 1.3 java版本： ####

public class BinarySearch_upper {
        
    
        /**
         * 查找 > target 的最小值的索引
         */
        public static int upper(int[] arr, int target) {
        
            int left = 0;
            int right = arr.length;
            // 循环不变量：在arr[left, right]的范围中查找解
            while (left < right) {
        
                int mid = left + (right - left) / 2;
                System.out.println("target = " + target + "; arr[mid] = " + arr[mid] + "; mid = " + mid);
                if (arr[mid] <= target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid;
                }
            }
            return left;
        }
    
        public static void main(String[] args) {
        
            int arr[] = {
        3, 5, 11, 17, 17, 21, 23, 101};
            int result = upper(arr, 11);
            System.out.println("result = " + result);
        }
    }

输出结果：

target = 11; arr[mid] = 17; mid = 4
    target = 11; arr[mid] = 11; mid = 2
    target = 11; arr[mid] = 17; mid = 3
    result = 3
    
    Process finished with exit code 0

### 2、lower：查找小于target的最大值 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]

#### 2.1 C++版本 ####

#include <iostream>
    
    // 二分查找法：查找小于target的最大值
    
    int lower(int arr[], int left, int right, int target) {
        
        while (left < right) {
        
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] == target) {
        
                right = mid - 1;
            } else if (arr[mid] > target) {
        
                right = mid - 1;
            } else {
        
                left = mid;
            }
        }
        return left;
    }
    
    int main() {
        
        int arr[] = {
        3, 5, 11, 17, 21, 23, 101, 101};
        int len = sizeof(arr) / sizeof(arr[0]);
        int target = 17;
        int result = lower(arr, -1, len - 1, target);
        std::cout << "result = " << result << std::endl;
    }

#### 2.2 python版本【坑： m i d = l e f t + ( r i g h t − l e f t + 1 ) / / 2 mid = left + (right - left + 1) // 2 mid=left\+(right−left\+1)//2下取整改为上取整，防止死循环】 ####

class Solution:
        """二分查找法：查找小于target的最大值"""
    
        def lower(self, nums, target):
            # 初始化查找范围
            left, right = -1, len(nums) - 1
    
            # 循环不变量：在nums[left, right]左闭右开区间查找小于target的最大值
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left + 1) // 2    # +1 防止 进入 left = mid 时下取整后进入死循环
                if nums[mid] == target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] == target，所以mid处的元素绝不可能是要找的值，排除掉】
                elif nums[mid] > target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] > target，所以mid处的元素绝不可能是要找的值，排除掉】
                else:  # nums[mid] < target
                    left = mid  # 继续在nums[mid, right] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return right

比如：查找小于60的最大值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.lower(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = -1---right = 7
    本轮循环结束：left = -1---right = 2
    
    left = -1---right = 2
    本轮循环结束：left = 1---right = 2
    
    left = 1---right = 2
    本轮循环结束：left = 2---right = 2
    
    
    最终：result =  2

比如：查找小于23的最大值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 23
    result = solution.lower(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = -1---right = 7
    本轮循环结束：left = -1---right = 2
    
    left = -1---right = 2
    本轮循环结束：left = -1---right = 0
    
    left = -1---right = 0
    本轮循环结束：left = -1---right = -1
    
    
    最终：result =  -1

比如：查找小于10的最大值

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 10
    result = solution.lower(nums, target)
    print("\n最终：result = ", result)

打印结果：

#### 2.3 java版本 ####

public class BinarySearch_lower {
        
    
        /**
         * 查找 < target 的最大值的索引
         */
        public static int lower(int[] arr, int target) {
        
            int left = -1;
            int right = arr.length - 1;
            // 循环不变量：在arr[left, right]的范围中查找解
            while (left < right) {
        
                int mid = left + (right - left + 1) / 2;
                System.out.println("target = " + target + "; arr[mid] = " + arr[mid] + "; mid = " + mid);
                if (arr[mid] < target) {
        
                    left = mid;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    
        public static void main(String[] args) {
        
            int arr[] = {
        3, 5, 11, 17, 17, 21, 23, 101};
            int result = lower(arr, 11);
            System.out.println("result = " + result);
        }
    }

输出结果：

target = 11; arr[mid] = 17; mid = 3
    target = 11; arr[mid] = 5; mid = 1
    target = 11; arr[mid] = 11; mid = 2
    result = 1
    
    Process finished with exit code 0

## 三、二分法查找法变种组合：upper\_ceil、lower\_ceil ##

### 1、upper\_ceil ###

*  如果存在元素，返回该元素最大索引
 *  如果元素不存在，返回比该元素大的最小值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]

#### 1.1 python版本 ####

比如：查找56

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 56
    result = solution.upper_ceil(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = 0---right = 8
    本轮循环结束：left = 0---right = 4
    
    left = 0---right = 4
    本轮循环结束：left = 3---right = 4
    
    left = 3---right = 4
    本轮循环结束：left = 3---right = 3
    
    
    最终：result =  2

比如：查找60

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.upper_ceil(nums, target)
    print("\n最终：result = ", result)

打印结果：

#### 1.2 java版本： ####

public class BinarySearch_ceil {
        
    
        /**
         * 查找 > target 的最小值的索引
         */
        public static int upper(int[] arr, int target) {
        
            int left = 0;
            int right = arr.length;
            // 循环不变量：在arr[left, right]的范围中查找解
            while (left < right) {
        
                int mid = left + (right - left) / 2;
                System.out.println("target = " + target + "; arr[mid] = " + arr[mid] + "; mid = " + mid);
                if (arr[mid] <= target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid;
                }
            }
            return left;
        }
    
        public static int ceil(int[] arr, int target) {
        
            int u = upper(arr, target);
            if (u - 1 >= 0 && arr[u - 1] == target) {
        
                return u - 1;
            }
            return u;
        }
    
        public static void main(String[] args) {
        
            int arr[] = {
        3, 5, 11, 17, 17, 21, 23, 101};
            int result01 = ceil(arr, 11);
            System.out.println("result01 = " + result01);
            System.out.println("===========================================");
            int result02 = ceil(arr, 13);
            System.out.println("result02 = " + result02);
        }
    }

输出结果：

target = 11; arr[mid] = 17; mid = 4
    target = 11; arr[mid] = 11; mid = 2
    target = 11; arr[mid] = 17; mid = 3
    result01 = 2
    ===========================================
    target = 13; arr[mid] = 17; mid = 4
    target = 13; arr[mid] = 11; mid = 2
    target = 13; arr[mid] = 17; mid = 3
    result02 = 3
    
    Process finished with exit code 0

### 2、lower\_ceil（>=target的最小索引） ###

*  如果该元素存在，返回该元素最小索引
 *  如果该元素不存在，返回大于该元素的最小索引

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]

class Solution:
    
        def upper(self, nums, target):
            # 初始化查找范围
            left, right = 0, len(nums)
    
            # 循环不变量：在nums[left, right]左闭右开区间查找大于target的最小值
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找目标值【由于nums[mid] == target，所以mid处的元素绝不可能是要找的值，排除掉】
                elif nums[mid] < target:
                    left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找目标值【由于nums[mid] < target，所以mid处的元素绝不可能是要找的值，排除掉】
                else:  # nums[mid] > target
                    right = mid  # 继续在nums[left, mid] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return left
    
        def lower_ceil(self, nums, target):
            upper_idx = self.upper(nums, target)
            while upper_idx - 1 >= 0 and nums[upper_idx - 1] == target:
                upper_idx -= 1
            return upper_idx

比如：查找56

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 56
    result = solution.lower_ceil(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = 0---right = 8
    本轮循环结束：left = 0---right = 4
    
    left = 0---right = 4
    本轮循环结束：left = 3---right = 4
    
    left = 3---right = 4
    本轮循环结束：left = 3---right = 3
    
    
    最终：result =  1

比如：查找60

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.lower_ceil(nums, target)
    print("\n最终：result = ", result)

打印结果：

## 四、二分法查找法变种组合：lower\_floor、upper\_floor ##

### 1、lower\_floor ###

*  如果该元素存在，返回该元素最小索引
 *  如果该元素不存在，返回小于该元素的最大索引

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]

class Solution:
    
        def lower(self, nums, target):
            # 初始化查找范围
            left, right = -1, len(nums) - 1
    
            # 循环不变量：在nums[left, right]左闭右开区间查找小于target的最大值
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left + 1) // 2    # +1 防止 进入 left = mid 时下取整后进入死循环
                if nums[mid] == target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] == target，所以mid处的元素绝不可能是要找的值，排除掉】
                elif nums[mid] > target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] > target，所以mid处的元素绝不可能是要找的值，排除掉】
                else:  # nums[mid] < target
                    left = mid  # 继续在nums[mid, right] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return right
    
        def lower_floor(self, nums, target):
            lower_idx = self.lower(nums, target)
            if lower_idx + 1 <= len(nums) - 1 and nums[lower_idx + 1] == target:
                lower_idx += 1
    
            return lower_idx

比如：查找69

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 69
    result = solution.lower_floor(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = -1---right = 7
    本轮循环结束：left = 3---right = 7
    
    left = 3---right = 7
    本轮循环结束：left = 3---right = 4
    
    left = 3---right = 4
    本轮循环结束：left = 3---right = 3
    
    
    最终：result =  4

比如：查找60

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.lower_floor(nums, target)
    print("\n最终：result = ", result)

打印结果：

### 2、upper\_floor（<=target的最大索引） ###

*  如果该元素存在，返回该元素最大索引
 *  如果该元素不存在，返回小于该元素的最大索引

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]

class Solution:
    
        def lower(self, nums, target):
            # 初始化查找范围
            left, right = -1, len(nums) - 1
    
            # 循环不变量：在nums[left, right]左闭右开区间查找小于target的最大值
            # 由于待搜索数组空间为左闭右开，如果当left == right，说明要搜索的数组已经是空数组
            while left < right:
                print("left = {0}---right = {1}".format(left, right))
                mid = left + (right - left + 1) // 2    # +1 防止 进入 left = mid 时下取整后进入死循环
                if nums[mid] == target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] == target，所以mid处的元素绝不可能是要找的值，排除掉】
                elif nums[mid] > target:
                    right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找目标值【由于nums[mid] > target，所以mid处的元素绝不可能是要找的值，排除掉】
                else:  # nums[mid] < target
                    left = mid  # 继续在nums[mid, right] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】
                print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))
    
            return right
    
        def upper_floor(self, nums, target):
            lower_idx = self.lower(nums, target)
            while lower_idx + 1 <= len(nums) - 1 and nums[lower_idx + 1] == target:
                lower_idx += 1
    
            return lower_idx

比如：查找60

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 60
    result = solution.upper_floor(nums, target)
    print("\n最终：result = ", result)

打印结果：

比如：查找56

solution = Solution()
    nums = [23, 56, 56, 65, 69, 69, 99, 99]
    target = 56
    result = solution.upper_floor(nums, target)
    print("\n最终：result = ", result)

打印结果：

left = -1---right = 7
    本轮循环结束：left = -1---right = 2
    
    left = -1---right = 2
    本轮循环结束：left = -1---right = 0
    
    left = -1---right = 0
    本轮循环结束：left = 0---right = 0
    
    
    最终：result =  2

## 五、二分法查找法模板 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020102713370314.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210610130227635.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210610130412895.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210610134807714.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210610135121267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210503175931775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210503175817365.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210503175641840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210503175728714.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210503180336582.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center