首页 > 代码库 > 二分法
二分法
@font-face { font-family: "宋体"; }@font-face { font-family: "Cambria Math"; }@font-face { font-family: "@宋体"; }@font-face { font-family: "Cambria"; }p.MsoNormal, li.MsoNormal, div.MsoNormal { margin: 0cm 0cm 0.0001pt; text-align: justify; font-size: 12pt; font-family: Cambria; }p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph { margin: 0cm 0cm 0.0001pt; text-align: justify; text-indent: 21pt; font-size: 12pt; font-family: Cambria; }.MsoChpDefault { font-family: Cambria; }div.WordSection1 { page: WordSection1; }ol { margin-bottom: 0cm; }ul { margin-bottom: 0cm; }
二分法是从一个已排序好的数列中寻找给定数值位置的算法
它从数列的中间的数字开始
1假如中间的数字和给定的数字相等,那么给定数值的位置就是在数列的中间
2如果中间的数字比给定数值小,那么给定数值的位置就是在数列的后半部分
3如果中间的数字比给定数值大,那么给定数值的位置就是在数列的前半部分
因此,寻找的数列经过每次寻找后都会减少一半
首先,这数列必须是非递减的
[low,high]代表这个数列的范围,[mid]代表数列中间的数字,low初始化为0.high初始化等于数列中数字的个数,mid=floor((low+high)/2).在每经一次二分算法后,减少寻找范围的一半。直到low<=high
- 如果(mid)
小于key(给定要寻找的数字),那么key就是出现在范围[mid+1,high],所以此时low=mid+1,high的值不变,mid相应地改变 - 如果(mid)等于key,那么key就是(mid)
- 如果(mid)大于key,那么key就是出现在范围[low
,mid
-1],所以此时high=[mid
-1],low
保持不变,mid相应改变
属性
1最好——(mid
)=key
,一次解决
2,最坏——key不在这个数列中,经过logN次算法,N为数列中得元素个数
3一般——key在数列中,但不是(mid),经过logN次算法
4数列必须已经排序
5它比线性搜索快,并且随着N变大,效果更加显著
二分法