首页 > 代码库 > 二分法

二分法

@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

  1. 如果(mid)
    小于key(给定要寻找的数字),那么key就是出现在范围[mid+1,high],所以此时low=mid+1,high的值不变,mid相应地改变
  2. 如果(mid)等于key,那么key就是(mid)
  3. 如果(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变大,效果更加显著

二分法