二分法查找(Binary Search)

时间:2023-03-08 22:11:30
二分法查找(Binary Search)

--摘要:二分法的介绍已经很多了,但并不直观,因此此文诞生,希望批评指正。

二分查找是在有序数组中查找一个元素的算法,通过比较目标元素与数组中间元素来查找,如果目标值是中间元素则将返回中间元素位置。

如果目标元素较小,则继续查找小于中间元素部分,如果目标元素较大,则继续查找大于中间元素部分。直到查找成功并返回其位置,或查到失败返回。

例在 2,5,7,8,10,15,18,20,22,25,28中查找18,简要图示,下文有更详细分布图例:

二分法查找(Binary Search)

C语言实现

函数原型:

int binary_search(int *array, int imin, int imax, int key)

 /**
* return the index of key.
* return -1 when failed.
*/
int binary_search(int *array, int imin, int imax, int key)
{
int imid; if(array == NULL || imin > imax) {
return -;
} while(imin <= imax) {
imid = imin + (imax - imin) / ; //avoid integer overflow
if(array[imid] == key) {
return imid;
} else if(array[imid] > key) {
imax = imid - ;
} else {
imin = imid + ;
}
} return -;
}

需要注意:

中间元素的查找方法不能为imid = ( imin + imax ) / 2,这样可能会造成整数溢出,因此应改为imid = imin + (imax – imin) / 2。

整数溢出:两个大整数相加其结果超过寄存器能存储的最大值,结果不可知。

图解说明:

array: 2   5   7   8   10   15   18   20   22   25   28

length:11

key: 18

imax = length - 1 = 10

imin = 0

步骤1:

imid = ( imin + imax ) / 2 = (0 + 10) / 2 = 5

二分法查找(Binary Search)

步骤2:

imid = ( imin + imax ) / 2 = (6 + 10) / 2 = 8  imax = imid -1 = 7

二分法查找(Binary Search)

步骤3:

imid = ( imin + imax ) / 2 = (6 + 7) / 2 = 6  find 18: index is 6

二分法查找(Binary Search)

原码下载地址: 
https://github.com/zsirGitHub/algorithms