找出指定数在数组中的范围

1. 因为题目要求时间复杂度是O(logn)，故不能用简单的遍历方式查找，需要使用二分查找的方式。注意：这里在用二分查找法找到目标数字后，不能使用从该位置逐一往前或往后判断值是否仍然是目标数的“线性探测”方法做，因为可能会有以下一种情况：输入数组的所有元素值都是目标数，这样的话用二分+线性探测的方式的复杂度是O(n)。
2. 这道题主要考察的点是二分的使用、是否对边界情况考虑周全。
3. 以下是java实现的代码，有详细注释(所以看着好像很长，但原理很简单)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int target = scanner.nextInt();
        scanner.nextLine();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        // begin和end分别为数组的起始和结束位置
        int begin = 0;
        int end = n - 1;
        // beginFoundLocation记录找到的目标值第一次出现的地方
        int beginFoundLocation = -1;
        // endFoundLocation 记录找到的目标值最后一次出现的地方
        int endFoundLocation = -1;
        endFoundLocation = findLastLocation(begin, end, arr, target);
        beginFoundLocation = findFirstLocation(begin, end, arr, target);
        System.out.println("[" + beginFoundLocation + "," + endFoundLocation + "]");
    }
    // 在arr数组的begin到end的范围内，寻找target第一次出现的位置
    public static int findFirstLocation(int begin, int end, int[] arr, int target) {
        // 记录中间点的位置及其值
        int middle = 0;
        int middleValue = arr[0];
        while (begin <= end) {
            middle = begin + (end - begin) / 2;
            middleValue = arr[middle];
            /*    
             * 二分查找：当中间位置点的值比target要小的时候就将寻找的起始位置（begin）设置为中间位置的下一个位置，
             * 当中间位置点的值比target要大的时候就将寻找的终止位置（end）设为中间位置的下一个位置 */
            /*
             * 注意：当中间位置的点的值正好是target的时候，需要看该位置的前一个位置点的值是否也为target，这就分为以下
             * 三种情况
             * 1.可能此时中间位置已经是0，也就是指向了数组的
             * 第一个元素，它没有前一个位置点，说明target第一次出现的位置就是0
             * 2.中间位置不是0，而且中间位置的前一个位置的值也是target，则继续用二分法在前面查找target
             * （注：这里不能用线性探测的方法，因为当输入数组元素值全部正好是target的时候，就成了遍历整个数组前半段，
             * 同理找最后target出现的位置也不能用线性探测法）。
             * 3.中间位置不是0，而且中间位置的前一个位置的值不是target，则正好该中间位置就是target第一次出现的位置，
             * 返回就好了。
             */
            if (middleValue < target) {
                begin = middle + 1;
            } else if (middleValue > target) {
                end = end - 1;
            } else if (middle > 0 && arr[middle - 1] == target) {
                end = middle - 1;
            } else if (middle > 0 && arr[middle - 1] != target) {
                return middle;
            } else if (middle == 0) {// 这里需要判定下，因为会有begin=end=0的情况，会死循环。
                return 0;
            }
        }
        // 当循环条件不满足的时候，可能是找到了target第一次出现的位置，也可能是target根本不在数组中
        if (arr[middle] != target) {
            return -1;
        } else {
            return middle;
        }
    }
    // 寻找target最后出现的位置，具体原理和寻找最初出现的位置相似
    public static int findLastLocation(int begin, int end, int[] arr, int target) {
        int middle = 0;
        int middleValue = arr[0];
        int lastArr = arr.length - 1;
        while (begin <= end) {
            middle = begin + (end - begin) / 2;
            middleValue = arr[middle];
            if (middleValue < target) {
                begin = middle + 1;
            } else if (middleValue > target) {
                end = end - 1;
            } else if (middle < lastArr && arr[middle + 1] == target) {
                begin = middle + 1;
            } else if (middle < lastArr && arr[middle + 1] != target) {
                return middle;
            } else if (middle == lastArr) {// 同样是为了防止死循环，需要判断下
                return lastArr;
            }
        }
        if (arr[middle] != target) {
            return -1;
        } else {
            return middle;
        }
    }
}

与归并排序算法有异曲同工之处

#include
using namespace std;
const int MAXN=1e5;
//int ans[MAXN];
int arr[MAXN];
int a=MAXN;
int b=-1;
void partition(int target,int left,int right)
{
    //如果是只剩下一个元素就不需要再进行分割了
    int mid=left+(right-left)/2;
    if(arr[mid]==target)
    {
       if(mid<a)
       {
           a=mid;
       }

        if(mid>b)
            b=mid;
    }
    if(left==right)
    {
        return ;
    }

        partition(target,left,mid);
        partition(target,mid+1,right);

    return;
}
int main()
{
    int n,target;

    cin>>n>>target;

    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }

     partition(target,0,n-1);

     if(a==MAXN)
    {
        a=-1;
    }
    cout<<'['<<a<<','<<b<<']'<<endl;

    return 0;

}

	import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int target = scan.nextInt();
        scan.nextLine();
        int[] nums = new int[n];
        for(int i=0; i<n; i++){
            nums[i] = scan.nextInt();
        }
        System.out.println("["+searchRange(nums,target)[0]+","+searchRange(nums,target)[1]+"]");
    }
    public static int[] searchRange(int[] nums, int target) {
        int[] ans = {-1,-1};
        if(nums == null || nums.length == 0) return ans;
        int low = 0, high = nums.length-1;
        if(low == high && nums[0] == target) return new int[] {0,0};
        while(low < high){
            int mid = low + (high-low)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else{
                high = mid;
            }
            if(low == high && nums[low] == target){
                ans[0] = low;
            }
        }
        low = 0; high = nums.length-1;
        while(low < high){
            int mid = low + (high-low+1)/2;
            if(nums[mid] > target){
                high = mid - 1;
            }else{
                low = mid;
            }
            if(low == high && nums[low] == target){
                ans[1] = low;
            }
        }
        return ans;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int target = sc.nextInt();
        int x = 0;
        int[] numbers = new int[n];
        while (x < n && sc.hasNext()) {
            numbers[x] = sc.nextInt();
            x++;
        }
        int lower = getLower(numbers, target, n);
        int upper = getUpper(numbers, target, n);
        System.out.println("[" + lower + "," + upper + "]");
        sc.close();
    }

    private static int getUpper(int[] numbers, int target, int length) {
        int start = 0;
        int end = length - 1;
        int mid = (start + end) / 2;
        int record = -1;
        while(start <= end){
            if(numbers[mid] <= target){
                if (numbers[mid] == target) record = mid;
                start = mid + 1;
                //if (numbers[mid] < target && start > end) return -1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) / 2;
        }
        if (record == -1) return -1;
        return end;
    }

    private static int getLower(int[] numbers, int target, int length) {
        int start = 0;
        int end = length - 1;
        int mid = (start + end) / 2;
        int record = -1;
        while(start <= end){
            //System.out.println("mid:" + mid);
            //System.out.println("record:" + record);
            if (numbers[mid] == target) record = mid;
            if (numbers[mid] < target){
                start = mid + 1;
                //if (start > end && record == 0) return -1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) / 2;
        }
        if (record == -1) return -1;
        return start;
    }
}