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

2024-09-02 04:08
文章标签 算法 数据 元素 二分 查找 复杂度 时间 有序 重复 结构 search 搜索算法 必须 binary logn 待查 前置条件

本文主要是介绍算法-搜索算法：二分查找（Binary Search）【前置条件：待查数据集必须是有序结构，可以右重复元素】【时间复杂度：O(logn)】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

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

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

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

一、二分法查找指定数值

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 // 2if alist[mid] == item:return Trueelif item < alist[mid]:return binary_search(alist[:mid], item)else:return binary_search(alist[mid + 1:], item)return Falseif __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]的范围中查找 targetwhile (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 = 5Process 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) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1  # 继续在nums[left, mid - 1] 范围内寻找targetelse:left = mid + 1  # 继续在nums[mid + 1, right] 范围内寻找targetprint("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return -1solution = 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 = 8left = 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) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid  # 继续在nums[left, mid) 范围内寻找targetelse:left = mid + 1  # 继续在nums[mid + 1, right) 范围内寻找targetprint("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return -1solution = 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 = 9left = 5---right = 9
本轮循环结束：left = 5---right = 7left = 5---right = 7
本轮循环结束：left = 5---right = 6left = 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)]】

在这里插入图片描述
在这里插入图片描述

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) // 2if 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] > targetright = 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 = 4left = 0---right = 4
本轮循环结束：left = 3---right = 4left = 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 = 8left = 5---right = 8
本轮循环结束：left = 7---right = 8left = 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)

打印结果：

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

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 = 3Process finished with exit code 0

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

在这里插入图片描述
在这里插入图片描述

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] < targetleft = 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 = 2left = -1---right = 2
本轮循环结束：left = 1---right = 2left = 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 = 2left = -1---right = 2
本轮循环结束：left = -1---right = 0left = -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)

打印结果：

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

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 = 1Process finished with exit code 0

三、二分法查找法变种组合：upper_ceil、lower_ceil

1、upper_ceil

  • 如果存在元素，返回该元素最大索引

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

在这里插入图片描述

1.1 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) // 2if 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] > targetright = mid  # 继续在nums[left, mid] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return leftdef upper_ceil(self, nums, target):upper_idx = self.upper(nums, target)if upper_idx - 1 >= 0 and nums[upper_idx - 1] == target:upper_idx -= 1return upper_idx

比如：查找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 = 4left = 0---right = 4
本轮循环结束：left = 3---right = 4left = 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)

打印结果：

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

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 = 3Process finished with exit code 0

2、lower_ceil（>=target的最小索引）

  • 如果该元素存在，返回该元素最小索引

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

在这里插入图片描述

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) // 2if 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] > targetright = mid  # 继续在nums[left, mid] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return leftdef lower_ceil(self, nums, target):upper_idx = self.upper(nums, target)while upper_idx - 1 >= 0 and nums[upper_idx - 1] == target:upper_idx -= 1return 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 = 4left = 0---right = 4
本轮循环结束：left = 3---right = 4left = 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)

打印结果：

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

四、二分法查找法变种组合：lower_floor、upper_floor

1、lower_floor

  • 如果该元素存在，返回该元素最小索引

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

在这里插入图片描述

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] < targetleft = mid  # 继续在nums[mid, right] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return rightdef 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 += 1return 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 = 7left = 3---right = 7
本轮循环结束：left = 3---right = 4left = 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)

打印结果：

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

2、upper_floor（<=target的最大索引）

  • 如果该元素存在，返回该元素最大索引

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

在这里插入图片描述

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] < targetleft = mid  # 继续在nums[mid, right] 范围内寻找目标值【此mid处的元素也有可能是答案，不能排除】print("本轮循环结束：left = {0}---right = {1}\n".format(left, right))return rightdef 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 += 1return 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)

打印结果：

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

比如：查找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 = 2left = -1---right = 2
本轮循环结束：left = -1---right = 0left = -1---right = 0
本轮循环结束：left = 0---right = 0最终：result =  2

五、二分法查找法模板

在这里插入图片描述

这篇关于算法-搜索算法：二分查找（Binary Search）【前置条件：待查数据集必须是有序结构，可以右重复元素】【时间复杂度：O(logn)】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1128947。

相关文章

大模型研发全揭秘：客服工单数据标注的完整攻略

大模型研发全揭秘：客服工单数据标注的完整攻略

在人工智能（AI）领域，数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者，掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中，工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注，不仅能够帮助提升客服自动化系统的智能化水平，还能优化客户服务流程，提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于MySQL Binlog的Elasticsearch数据同步实践

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展，我们的业务数据越来越多，单纯使用 MySQL 已经不能满足我们的数据查询需求，例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后，随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步，我们目前的解决方案是建立数据中间表。把需要检索的业务数据，统一放到一张M
阅读更多...
服务器集群同步时间手记

服务器集群同步时间手记

1.时间服务器配置（必须root用户） （1）检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 （2）修改ntp配置文件 [r
阅读更多...
关于数据埋点，你需要了解这些基本知识

关于数据埋点，你需要了解这些基本知识

产品汪每天都在和数据打交道，你知道数据来自哪里吗？ 移动app端内的用户行为数据大多来自埋点，了解一些埋点知识，能和数据分析师、技术侃大山，参与到前期的数据采集，更重要是让最终的埋点数据能为我所用，否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式，可以区分为： 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理：自动程度高的，能解决通用统计，便于统一化管理，但个性化定
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
异构存储（冷热数据分离）

异构存储（冷热数据分离）

异构存储主要解决不同的数据，存储在不同类型的硬盘中，达到最佳性能的问题。 异构存储Shell操作 （1）查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies （2）为指定路径（数据存储目录）设置指定的存储策略 hdfs storagepolicies -setStoragePo
阅读更多...
Hadoop集群数据均衡之磁盘间数据均衡

Hadoop集群数据均衡之磁盘间数据均衡

生产环境，由于硬盘空间不足，往往需要增加一块硬盘。刚加载的硬盘没有数据时，可以执行磁盘数据均衡命令。（Hadoop3.x新特性） plan后面带的节点的名字必须是已经存在的，并且是需要均衡的节点。 如果节点不存在，会报如下错误： 如果节点只有一个硬盘的话，不会创建均衡计划： （1）生成均衡计划 hdfs diskbalancer -plan hadoop102 （2）执行均衡计划 hd
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2