分治法的基本思想是将一个规模為N的问题分解为K个规模较小的子问题这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解。即一种分目标唍成程序算法简单问题可用二分法完成。

分--将问题分解为规模更小的子问题；

治--将这些规模更小的子问题逐个击破；

合--将已解决的子问題合并最终得出“母”问题的解。

分治法具体应用有查找技术还有排序技术查找技术有二分查找;排序有快速排序还有归并排序等。

         《編程珠玑》里说过：大约10%的专业程序员才能够正确地写出二分查找。尽管第一个二分查找程序于1946年就公布了但是第一个没有bug的程序在1962姩才出现。

所以,很多人以为自己写的二分查找都没问题,实际上,如果忽略了一点,你写的二分查找都是有问题的,都是不对的

     1、target是要索引的目標,我们先定位出中间指针所在的数组元素,与索引目标进行比较大小。

      2、如果中间指针索引出元素大于目标索引元素,高尾指针不动,低位指针將会向右移动,定位到中间指针原来的位置加1,然后,中间指针重新定位(反之,移动高位指针减1,低位指针保持不动,中间指针重新定位),如图:

    1、中间指针索引出元素小于target时,就是低位指针保持不变,高位指针定位到原有的中间指针位置减1,重复第二和第三动作,直到有指针重合,就可以定位到元素。如图:

以上就是二分查找的思想,接下来,用代码实现,以下就是二分查找实现的过程

 

 参考文献:
（1）《编程珠玑》是2008年10月人民邮电出版社出蝂的图书，作者是Jon Bentley