数据结构与算法之二分查找分而治之思想

决定我们成为什么样人的，不是我们的能力，而是我们的选择。——《哈利·波特与密室》

二分查找是查找算法里面是很优秀的一个算法，特别是在有序的数组中，这种算法思想体现的淋漓尽致。

一.题目描述及其要求

请实现无重复数字的升序数组的二分查找：

给定一个 元素升序的、无重复数字的整型数组 arr和一个目标值 target ，写一个函数搜索 arr中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1.

示例一：

输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在arr中并且下标为 6 

示例二：

输入：[],3
返回值：-1
说明：arr为空，返回-1  

示例三：

输入：[-1,0,3,4,6,10,13,14],2
返回值：-1
说明：2 不存在arr中因此返回 -1 

二.分治思想

分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

1.逐个遍历思路：

本来我们可以遍历数组直接查找，每次检查当前元素是不是要找的值。

for(int i = 0; i <length; i++)if(arr[i] == target)return i;

2.逐个遍历出现的问题

但是这样这个有序的数组我们就没有完全利用起来。

我们想想，若是目标值比较小，肯定在前半区间，若是目标值比较大，肯定在后半区间，怎么评价大小？我们可以用中点值作为一个标杆，将整个数组分为两个区间，目标值与中点值比较就能知道它会在哪个区间，这就是分治的思维。

三分治思想具体做法：

• step 1：从数组首尾开始，每次取中点值。

• step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。

• step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到

代码实现：

int search(int*arr, int length, int target ) {if(length == 0) return -1;int left=0, right=length-1;while(left<=right) {int mid = left+(right-left)/2;if(arr[mid]==target) return mid;if(arr[mid]<target) left=mid+1;if(arr[mid]>target) right=mid-1;}return -1;
}

ps：int mid = left+(right-left)/2;与int mid=(left+right)/2是一样的，但是选择前者更安全，因为后者两个整数相加数据过于庞大可能会出现数据溢出的情况，所以采用前者更加可靠。

也可以这样写：mid = left+(right-left >> 1); +-大于位移运算的优先级 左移*2

本算法到这，其实二分查找可以分为几种情况来讨论，这里提供一种比较好理解的方案，具体算法大家可以参考相应资料自了解，大家加油。。。。。最近在做算法题目可以关注我，点个赞，有问题可以一起讨论。以后的几篇文章都讲解算法的题目。