大家都知道使用BINARY SEARCH读取内表时效率要高很多,那么如果要取的值有多条,那么应该取第几个条的呢?
如:1 2 3 3 3 4 5 6 7 8 9,需要读取3值,那么他读取的是哪个位置的3呢?
答案:根据二分法他会始终读取第三个位置的3,即同值3中的第一个。
百度中对二分法的定义:
二分法检索(binary search)又称折半检索,二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组(array)中,首先将给定值key与字典中间位置上元素的关键码(key)比较,如果相等,则检索成功;否则,若key小,则在字典前半部分中继续进行二分法检索;若key大,则在字典后半部分中继续进行二分法检索。
这样,经过一次比较就缩小一半的检索区间,如此进行下去,直到检索成功或检索失败。
偶数个取中间2个其中任何一个作为中间元素。
1 2 3 3 3 4 5 6 7 8 9
第一种情况:
- 1 2 3 3 3
- 123(取第三个位置的三,即这里的最后一个)
33
- 12
33(取第三个位置的三,即这里的第一个)
- 123(取第三个位置的三,即这里的最后一个)
- 4 5 6 7 8 9 没有3,该行淘汰
第二种情况:
- 1 2 3 3 3 4
- 123(取第三个位置的三,即这里的最后一个)
- 334
- 5 6 7 8 9 没有3,该行淘汰
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/20110.html