数组算法——查询位置

需求

思路

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