c++ 二分查找及其变种
时间: 2024-01-19 18:00:46 浏览: 43
二分查找是一种高效的查找算法,适用于在已排序的数组中查找目标元素。其基本思想是将待查找范围不断二分,通过与目标元素进行比较来决定继续查找的方向,直到找到目标元素或确定不存在。
首先,设定初始的查找范围为整个数组,即左边界为0,右边界为数组长度减一。然后,计算中间位置的索引mid,获得对应的数组元素。
如果mid位置的元素等于目标元素,则找到目标,返回对应索引。
如果mid位置的元素大于目标元素,则目标元素应该在mid的左侧,更新右边界为mid-1。
如果mid位置的元素小于目标元素,则目标元素应该在mid的右侧,更新左边界为mid+1。
重复以上步骤,直到左边界大于右边界,表示整个数组已查找完毕,但未找到目标元素,返回-1。
二分查找的时间复杂度为O(log n),其中n为数组长度。
二分查找的变种有几种,例如:
1. 查找第一个匹配的元素
在循环过程中,如果mid位置的元素等于目标元素,但其前一个元素不等于目标元素,即找到第一个匹配的元素。
2. 查找最后一个匹配的元素
在循环过程中,如果mid位置的元素等于目标元素,但其后一个元素不等于目标元素,即找到最后一个匹配的元素。
3. 查找第一个大于目标元素的元素
在循环过程中,如果mid位置的元素大于目标元素,但其前一个元素小于或等于目标元素,即找到第一个大于目标元素的元素。
4. 查找最后一个小于目标元素的元素
在循环过程中,如果mid位置的元素小于目标元素,但其后一个元素大于或等于目标元素,即找到最后一个小于目标元素的元素。
这些变种通过稍微改变循环内的判断条件,可以在相同的时间复杂度下实现特定的查找需求。