二分查找(详尽版)

二分查找

给定一有序的序列nums[]，一个元素target，想要找到其中等于给定元素的下标。大体思路就是总是折半查找，通过比较给定元素与序列中间元素的大小，若nums[midIndex] > target,说明target的值在前半段，小于时在后半段。如此往复，即可得到结果。

算法如此简单，但在具体实现过程中有些细节问题值得思考。如下就列出五种情况下的的二分查找。

目录

1.从nums[]中找到target的任一位置；

2.从nums[]中找到target出现的第一个位置；

3.从nums[]中找到target出现的最后一个位置；

4.从nums[]中找到大于target出现的第一个位置；

5.从nums[]中找到小于target出现的最后一个位置； 

 

---

 

1.从nums[]中找到target的任一位置；

代码实现如下：

public static int search1(int[] nums, int target) { int minIndex = 0, maxIndex = nums.length - 1, midIndex = 0;; while(minIndex < maxIndex - 1) {//两个情况下退出来即可 midIndex = minIndex + (maxIndex - minIndex) / 2; if(nums[midIndex] < target) { minIndex = midIndex; }else if(nums[midIndex] > target) { maxIndex = midIndex; }else { break; } } if(nums[midIndex] == target) { return midIndex; }else if(nums[minIndex] == target) { return minIndex; }else if(nums[maxIndex] == target) { return maxIndex; }else { return -1; } }

注：上述实现过程中进行中值计算时并没有使用midIndex = (minIndex + maxIndex) / 2,这是由于这种做法可能引起越界问题，minIndex + maxIndex可能会超过Integer.MAX_VALUE。

2.从nums[]中找到target出现的第一个位置；

代码实现如下：

public static int search2(int[] nums, int target) { int minIndex = 0, maxIndex = nums.length - 1, midIndex = 0;; while(minIndex < maxIndex - 1) {//两个情况下退出来即可 midIndex = minIndex + (maxIndex - minIndex) / 2; if(nums[midIndex] >= target) { maxIndex = midIndex; }else{ minIndex = midIndex; } } if(nums[minIndex] == target) { return minIndex; }else if(nums[maxIndex] == target) { return maxIndex; }else { return -1; } }

大体实现类似，就是由于该题要找到是出现的第一个位置，因此对于出现nums[midIndex] == target的情况，应该把他归到n大于target中，在前半段寻找。

3.从nums[]中找到target出现的最后一个位置；

代码实现如下：

public static int search3(int[] nums, int target) { int minIndex = 0, maxIndex = nums.length - 1, midIndex = 0;; while(minIndex < maxIndex - 1) {//两个情况下退出来即可 midIndex = minIndex + (maxIndex - minIndex) / 2; if(nums[midIndex] <= target) { minIndex = midIndex; }else{ maxIndex = midIndex; } } if(nums[maxIndex] == target) { return maxIndex; }else if(nums[minIndex] == target) { return minIndex; }else { return -1; } }

由于需要找出现最后一个位置，应该把等于target的部分归结到小于target那块，在其后半段寻找。

4.从nums[]中找到大于target出现的第一个位置；

public static int search(int [] nums, int target) { int minIndex = 0, maxIndex = nums.length - 1, midIndex = 0; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(nums[midIndex] > target) { maxIndex = midIndex; }else { minIndex = midIndex; } } if(nums[minIndex] > target) { return minIndex; }else if(nums[maxIndex] > target) { return maxIndex; }else { return -1; } }

这个问题近似等于问题三，不过在后面返回时是从minIndex开始的。

5.从nums[]中找到小于target出现的最后一个位置；

代码实现如下：

public static int search1(int [] nums, int target) { int minIndex = 0, maxIndex = nums.length - 1, midIndex = 0; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(nums[midIndex] < target) { minIndex = midIndex; }else { maxIndex = midIndex; } } if(nums[maxIndex] < target) { return maxIndex; }else if(nums[minIndex] < target) { return minIndex; }else { return -1; } }

 抖个机灵，小于target的第一个元素下标要么为0，要么为-1，大于dateget的最后一个元素下标要么为length-1，要么为-1，我确定。

参考文献：

[1] 编程之美 : 微软技术面试心得[M]. 2008.