二分法查寻为什么每个元素查找次数为lgn
二分法查找为什么每个元素查找次数为lgn
书上说：“以二分査找的平均情况为例。假设数组的长度是2的幂，要查找的数字在数组的任意元素中的概率都是一样的，二分査找法在搜索时，首先杳找该数组的中间元素，第二次查找数组前半部分的屮间元素，或者査找数组后半部分的中间元素，第三次査找数组丨1/4、2/4、3/4或4/4 部分的屮间元素，第四次查找数组1/8、2/8、…、7/8或8/8部分的中间元素，以此类推，因此, 二分査找法会在第一个元素屮尝试lg n次，或者在第三个元素中尝试lgn次……………… ”
问 为什么是lgn次？
------解决方案--------------------
是log2(n)
------解决方案--------------------
2^n = len
n = lg(len) / lg(2)
------解决方案--------------------
书上说：“以二分査找的平均情况为例。假设数组的长度是2的幂，要查找的数字在数组的任意元素中的概率都是一样的，二分査找法在搜索时，首先杳找该数组的中间元素，第二次查找数组前半部分的屮间元素，或者査找数组后半部分的中间元素，第三次査找数组丨1/4、2/4、3/4或4/4 部分的屮间元素，第四次查找数组1/8、2/8、…、7/8或8/8部分的中间元素，以此类推，因此, 二分査找法会在第一个元素屮尝试lg n次，或者在第三个元素中尝试lgn次……………… ”
问 为什么是lgn次？
------解决方案--------------------
是log2(n)
------解决方案--------------------
2^n = len
n = lg(len) / lg(2)
------解决方案--------------------