LintCode14.二分查找（binarySearch） Java实现

二分查找 给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。 样例

样例 1: 输入:[1,4,4,5,7,7,8,9,9,10]，1 输出: 0 没有出现过打印-1；

如果数组中没有重复元素，写出二分查找的代码很简单，如下

public int binarySearch(int[] nums, int target) { // write your code here int start=0; int end=nums.length-1; while (start<=end){ int mid=(start+end)/2; if (target==nums[mid]) { return mid; }else if (target>nums[mid]){ start=mid+1; } else{ end=mid-1; } } return -1; }

但是如果数组中出现重复的元素，因为要返回数组中出现的该元素的第一个位置，则需要调整代码，这也是这道题与单纯的二分查找不一样的地方。 思路引导：如果找到该元素，不能直接返回，而是要向左遍历，看左边是否还存在该元素，（如果还是不懂，建议debug一下）。

public int binarySearch(int[] nums, int target) { // write your code here int start=0; int end=nums.length-1; while (start<=end){ int mid=(start+end)/2; if (target==nums[mid]) {//找到与target相等元素，继续向左遍历 end=mid-1; }else if (target>nums[mid]){ start=mid+1; } else{ end=mid-1; } } if(target==nums[start]){//也可以写成target==nums[end+1] return start; }else{ return -1; } }

当遍历完整个数组后，start和end指针的相对位置是确定的，end=start-1，这就是为什么可以写成target==nums[end+1]；如果能理解这一点，我认为对这道题也就有一定的理解了。