关于java:求解非递减数组范围下标

题目

有序非递加数组，找出在指定区间中的元素地位，输入起始和完结地位的下标。
如数组：1,2,2,3,4,6
区间:2,8(大于等于 2，小于等于 8)
后果 1,5（1 是合乎区间最右边的下标，5 是合乎区间最左边的下标）
要求工夫复杂度要小于 O(N)(不能够是 O(N))

解法 1: 二分查找

private int[] array = {1,2,2,3,4,6};

private int min = -20;

private int max = 8;

public void binarySearch() {int left = binarySearch(array,min,true);
    int right = binarySearch(array,max,false);
    System.out.println(left +" "+ right);
}

private int binarySearch(int[] array,int target,boolean first){
    int length = array.length;
    if (length == 0) {return -1;}
    if (array[0] > max) {return -1;}
    if (array[length-1] < min) {return -1;}
    int left = 0,right = length -1;
    while (left <= right) {int mid = left + (right -left)/2;
        if (array[mid] > target) {right = mid - 1;}else if (array[mid] < target) {left = mid + 1;}else {if (first) {if (mid == 0 || array[mid - 1] != target) {return mid;} else {right = mid - 1;}
            } else {if (mid == 0 || array[mid + 1] != target) {return mid;} else {left = mid + 1;}
            }
        }
    }
    if (first) {return left;} else {return right;}
}

github 源码

本文由博客一文多发平台 OpenWrite 公布！