难以理解指数搜索的工作原理
Trouble in understanding how Exponential Search works
我正在为考试和学习搜索算法而学习。我了解线性、二进制和插值搜索,现在尝试了解指数搜索。但是网上有不好的来源,如果有解释对我来说很复杂..我希望你能澄清算法?
编辑(试图纠正我的错误):
假设我们有一个数组,我们在数组中搜索 19
:
Index i 0 1 2 3 4 5 6
2 7 13 19 55 92 99
我们先尝试找到范围(在哪个点划分数组)
2^0 : i=1: A[1] > 19
2^1 : i=2: A[2] > 19
2^2 : i=4: A[4] < 19
现在我们知道我们需要从索引 i=0
搜索到 i=3
。
现在我们使用二进制搜索来查找元素 19
我们当前的子数组是
Index i 0 1 2 3
2 7 13 19
我们在中间划分二分查找,所以我们有数组
13 19
现在再在中间分开。 19
大于 13
并且 19
现在只是数组中的元素。我们完成了,我们找到 19
现在正确吗?
指数搜索是一种用于搜索无限数组或大小未知的数组的算法。它有两个步骤:
1) 查找大于或等于该值的第一个元素的位置
2)从头到尾进行二分查找
第一步允许您定义二进制搜索的范围。并且由于指数增加的因素,它被称为指数搜索。
步骤 应该在搜索的指数阶段增加 。
您必须检查数组的第一个元素,然后是第二个、第四个、第八个、第十六个等等,直到检查的元素(编号为 2^k
)变得大于(或等于)值搜索。
此刻你知道搜索到的值在2^(k-1)..2^k
范围内,并在这个范围内开始二分查找
请注意,指数阶段允许快速找到包含搜索值的范围。
P.S。对于从零开始的数组计数,检查第 0 个索引很方便,然后开始索引序列 1,2,4,8,16...
我正在为考试和学习搜索算法而学习。我了解线性、二进制和插值搜索,现在尝试了解指数搜索。但是网上有不好的来源,如果有解释对我来说很复杂..我希望你能澄清算法?
编辑(试图纠正我的错误):
假设我们有一个数组,我们在数组中搜索 19
:
Index i 0 1 2 3 4 5 6
2 7 13 19 55 92 99
我们先尝试找到范围(在哪个点划分数组)
2^0 : i=1: A[1] > 19
2^1 : i=2: A[2] > 19
2^2 : i=4: A[4] < 19
现在我们知道我们需要从索引 i=0
搜索到 i=3
。
现在我们使用二进制搜索来查找元素 19
我们当前的子数组是
Index i 0 1 2 3
2 7 13 19
我们在中间划分二分查找,所以我们有数组
13 19
现在再在中间分开。 19
大于 13
并且 19
现在只是数组中的元素。我们完成了,我们找到 19
现在正确吗?
指数搜索是一种用于搜索无限数组或大小未知的数组的算法。它有两个步骤:
1) 查找大于或等于该值的第一个元素的位置 2)从头到尾进行二分查找
第一步允许您定义二进制搜索的范围。并且由于指数增加的因素,它被称为指数搜索。
步骤 应该在搜索的指数阶段增加 。
您必须检查数组的第一个元素,然后是第二个、第四个、第八个、第十六个等等,直到检查的元素(编号为 2^k
)变得大于(或等于)值搜索。
此刻你知道搜索到的值在2^(k-1)..2^k
范围内,并在这个范围内开始二分查找
请注意,指数阶段允许快速找到包含搜索值的范围。
P.S。对于从零开始的数组计数,检查第 0 个索引很方便,然后开始索引序列 1,2,4,8,16...