在何大神的博客看到一篇关于重复数据二分查找的题目。描述如下：

给定一个升序排列的自然数数组，数组中包含重复数字，例如：[1,2,2,3,4,4,4,5,6,7,7]。问题：给定任意自然数，对数组进行二分查找，返回数组正确的位置，给出函数实现。注：连续相同的数字，返回第一个匹配位置还是最后一个匹配位置，由函数传入参数决定。 

文章链接：http://hedengcheng.com/?p=595

下面是自己给出的一种实现，代码写的有点啰嗦，应该还有可以优化的地方。



//java语言描述
public class BinarySearch {
    public static void main(String[] args) {
        int[] tmp = {1,2,2,3,4,4,4,5,6,7,7};
        int target = 7;
        int result = BinarySearch.makeSearchLoop(target, tmp, 1);
        System.out.println(result);
    }
    public static int makeSearchLoop(int target,int[] arr,int tag) {
         if(arr.length == 0) {
             return -1;
         }
         int left=0,right=arr.length-1;
         while(left+1<right) {
             int mid = (left+right)/2;
             if(target > arr[mid]) {
                 left = mid+1;
             }
             if(target < arr[mid]) {
                 right = mid-1;
             }
             if(target == arr[mid] && tag == 0) {
                 right = mid;
             }
             if(target == arr[mid] && tag == 1) {
                 left = mid;
             }
         }
         if(arr[left]==arr[right] && arr[right]==target) {
             return left+tag;
         }
         if(arr[left] == target) {
             return left;
         }
         if(arr[right] == target) {
             return right;
         }
         return -1;
    }
}

非重复数据中的二分查找，在target == arr[mid]之后就可以return mid了。但既然是包含重复数据的数组，mid的位置就可能是其中的某一个。 

题目要求tag为0时返回最前面的位置，tag为1时返回最后面的位置。因此我们在target == arr[mid]之后还需要再根据tag的值继续进行判断，如果tag=0，则要得到的位置应该<=mid；如果tag=1，则要得到的位置应该>=mid。由于我们直接将mid赋给了left（或right），最后会出现只剩left和right分别对应两个元素的情况，因此在循环之后，需要对left和right位置上的值进行判断，有些啰嗦~