数组算法——查询位置

需求

思路

• 使用二分查找找到第一个值，以第一个值作为界限，分为左右两个区间
• 在左右两个区间分别使用二分查找
• 找左边的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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

右边索引

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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);
1
2
3
4
5
6