算法通关村第九关—二分查找模版(青铜)

? ? ? ? ? ? 二分查找模版

一、循环

public int binarySearch(int[] array,int low,int high,int target){
    while(low <= high){
        //注意尽量不写(low+high)/2
        //可以写出 low + (high - low) / 2
        int mid = low + ((high - low) >> 1);
        if (array[mid] == target) return mid;
        else if (array[mid] < target){
            //由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            high = mid - 1;
        }
        else{
            //由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            low = mid + 1;
        }
    }
    return -1;
}

二、递归

public int binarySearchl(int[] array,int low,int high,int target){
    //递归终止条件
    if(low <= high){
        int mid = low + ((high + low)>>1);
        if(array [mid] == target){
            return mid;//返回目标值的位置，从1开始
        }
        else if(array[mid] > target){
            //由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            return binarySearch(array,low,mid-1,target);
        }
        else{
            //由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            return binarySearch(array,mid+1,high,target);
        }
    }
    return -1; //表示没有搜索到
}

三、元素中有重复的二分查找

?假如在上面的基础上，元素存在重复，如果重复则找左侧第一个，请问该怎么做呢？
?这里的关键是找到目标结果之后不是返回而是继续向左侧移动。最简单的方式，就是找到相等位置向左使用线性查找，直到找到相应的位置。

public static int search(int[]nums,int target){
    if(nums == null || nums.length == 0) return -1;
    int left = 0;
    int right = nums.length - 1;
    while(left <= right){
        int mid = left + (right + left) / 2;
        if(nums[mid] < target){
            left = mid + 1;
        }
        else if(nums[mid] > target){
            right = mid - 1;
        }
        else{
            //找到之后，往左边找
            while(mid !=0 && nums[mid] == target)
            mid--;
            if(mid == 0 && nums[mid] == target){
                return mid;
            }
            return mid + 1;
        }
    }
    return -1;
}