数组算法——查询位置

需求

在这里插入图片描述

思路

使用二分查找找到第一个值，以第一个值作为界限，分为左右两个区间
在左右两个区间分别使用二分查找
找左边的7,：找到中间位置的7之后，将中间位置的7作为结束位置，依次循环查找，知道start>end,返回start，这就是7第一次出现的位置
找右边的7,：找到中间位置的7之后，将中间位置的7作为开始位置，依次循环查找，知道start>end,返回end，这就是7最后一次出现的位置

代码

左边索引

private static int getLeftIndex(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            end = mid - 1;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    if (start >= nums.length || nums[start] != target) {
        return -1;
    }
    return start;
}

右边索引

private static int getRightIndex(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            start = mid + 1;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    if (end < 0 || nums[end] != target) {
        return -1;
    }
    return end;
}

main函数返回
leftIndex = 3
rightIndex = 5

int[] nums = {1,3,3,7,7,7,8,8,9};
int target = 7;
int leftIndex = getLeftIndex(nums, target);
int rightIndex = getRightIndex(nums, target);
System.out.println("leftIndex = " + leftIndex);
System.out.println("rightIndex = " + rightIndex);