经典算法系列之:二分查找

seekerhit 2019-12-09

1、前言

算法,在计算机中的地位,就相当于人类大脑的决策中枢系统,哪怕最简单的算法,其精妙的思维方式,都可以让人开启一扇新的视窗。

算法,它不仅仅只是狭义的用来解决计算机科学领域的问题,更是一种“思维方式”。算法思维,是一种深度思考和创造的过程。

算法,只有真正理解了,而不只是所谓的知道,并将应用到生活、工作、学习等各个方面,它将一定使人受益终生。

2、原理推导

二分查找,前提是在排好序的基础上,每次查找,将数据集合分成两个部分,取中间索引数值与被查找的数值比较,逐次缩小查找范围,直到找到数值。

给定一组 {1,2,3,4,5,6} 的原始有序数组,按照从小到大升序排列。

经典算法系列之:二分查找

#step1

初始化低位索引为0,高位索引为数组长度减1索引为5,低位+高位除2,中间索引取整为:2=(0+5)/2,对应的数值就是数组中的3。
经典算法系列之:二分查找

#step2

第一次比较,数值【5】大于【3】,所以低位索引被修为3=2+1,对应数组中的数值【4】,高位索引不变还是5,低位+高位除2,中间索引取整为:4=(3+5)/2,对应的数值就是数组中的【5】。
经典算法系列之:二分查找

至此,二分查找已经完成,数值【5】在数组中的索引位置为:4 ,在本次查找过程中,我们只用到两次查找就找到了被查找的数值,大大提高了查询效率。

3、代码示例

# 排序是前提,假设已经是有序数组

public  int dichotomy(int array[],int data){??? 
int lowIndex = 0; // 初始化低位索引??? 
int hightIndex = array.length - 1; // 初始化高位索引???

//循环查找,直到找到或者到最后一个数跳出循环???
while (true) {???????
    int index = (lowIndex + hightIndex) / 2; // 求每次查找的中间索引,这是最重要的一步??????? 
    if (lowIndex > hightIndex){ // 低位索引大于高位索引则表示没有找到对应的数值,退出循环??????????? 
        return -1;??????? 
    }else if (array[index] == data) { // 两个数相等,则返回索引退出循环???????????
        return index;??????? 
    } else {???????????
         if (array[index] > data) { // 中间数值大于查找数值,则中间索引减1作为下一次查找的高位索引??????????????? 
        hightIndex = index - 1;???????????
    } else { // 中间数值小于查找数值,则中间索引加1作为下一次查找的低位索引
         lowIndex = index + 1;??????????? 
         }???????
      }??? 
    }
}

4、禅定时刻

二分查找,采用的是排除法,通过每一次的提问,大了还是小了逐步缩小范围。这种算法给我们提供的一种思维方式是:当我们面临多个选项时,我们无法准确定位是那个正确答案的时候,我们可以在现有答案中先缩小范围,再去选择,降低了选择和决策的成本。

作者简介

思维的持续,一个真的有思想,不穿格子衬衫的程序员。
经典算法系列之:二分查找

相关推荐