数组算法——查询位置

需求

思路

• 使用二分查找找到第一个值，以第一个值作为界限，分为左右两个区间
• 在左右两个区间分别使用二分查找
• 找左边的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);

原文地址：https://blog.csdn.net/qq_40603125/article/details/137674341

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！