java二分查找

二分查找针对的一定是有序数组啊，因为有序数组才知道每次分的方向。

//二分查找    
public static int binarySearch(int[] nums,int target){
        if(nums==null||nums.length==0){
            return -1;
        }
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //右移1位等于除以2。（left+right）/2的操作有可能溢出，这样的写法安全。
            int mid=left+((right-left)>>1);
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }

    // 随机生成一个不降序的数组
    public static int[] generateGrowArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        arr[0] = (int) (Math.random() * maxValue);
        for (int i = 1; i < len; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] < arr[i - 1]);
        }
        return arr;
    }

针对二分查找引申出来的有：查找>=target的最左位置；查找<=target的最右位置；局部最小值等问题。

1、查找>=target的最左位置（需要有序数组）

public int findMostLeftIndexNoLessNum(int[] nums, int target){
    if(nums==null||nums.length==0){
        return -1;
    }
    int left=0;
    int right=nums.length-1;
    int ans=-1;
    while(left<=right){
        int mid=left+(right-left)>>1;
        if(nums[mid]>=target){
            //记录下该>=target的位置
            ans=mid;
            //需要继续往左边搜索，是否还存在大于等于target的位置
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return ans;
}

2、查找<=target的最右位置（需要有序数组）

public int findMostRightIndexNoMoreNum(int[] nums, int target){
    if(nums==null||nums.length==0){
        return -1;
    }
    int left=0;
    int right=nums.length-1;
    int ans=-1;
    while(left<=right){
        int mid=left+(right-left)>>1;
        if(nums[mid]<=target){
            //记录下该<=target的位置
            ans=mid;
            //需要继续往右边搜索，是否还存在小于等于target的位置
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return ans;
}

3、局部最小值

局部最小值不需要有序数组，但需要保证相邻的两个数不相等，这样的数组一定存在局部最小值。我们约定对于int[] nums，如果nums[0]<nums[1]，则nums[0]为局部最小值；如果nums[n-2]>nums[n-1]，则nums[n-1]为局部最小值（n为数组长度）。

//返回一个局部最小值的位置
public int findPartMostMinIndex(int[] nums){
    if(nums==null||nums.length==0){
        return -1;
    }
    if(nums.length==1){
        return 0;
    }    
    if(nums[0]<nums[1]){
        return 0;
    }
    int n=nums.length-1;
    if(nums[n-1]>nums[n]){
        return n;
    }
    //因为首尾已经判断过了，所以可以不要首尾
    //也可以保证 nums[mid]和nums[mid+1]、nums[mid-1]比较时不越界 比如 数组[3 2 3 2 3]
    int left=1;
    int right=n-1;
    //一定存在一个局部最小，为什呢
    //0到1下降趋势 n-2到n-1上升趋势 所以0到n-1范围内一定存在一个局部最小值
    while(left<=right){
        int mid=left+(right-left)>>1;
        //nums[mid]每次都要和nums[mid+1]、nums[mid-1]比大小，所以要保证mid+1和mid-1要在数                                    组下标范围内，否则就会越界
        if(nums[mid]>nums[mid-1]){
            right=mid-1;
        }else if(nums[mid]>nums[mid+1]){
            left=mid+1;
        }else{
            //比左边小 比右边小 找到了
            return mid;
        }
    }
    return -1;
}     

//为了测试 写一个随机生成相邻数不相等的数组
public static int[] generateAdjacentNoEqualArray(int maxSize, int maxValue){
        int[] arr=new int[(int) (maxSize*Math.random()+1)];
        arr[0]=(int) ((maxValue)*Math.random());
        for (int i = 1; i < arr.length; i++) {
            //[0-maxValue-1]等概率返回一个整数
            do {
                arr[i]=(int) ((maxValue)*Math.random());
            }while (arr[i]==arr[i-1]);
        }
        return arr;
    }