【力扣】34.在排序数组中查找元素的第一个位置和最后一个位置

问题描述

思路解析

• 遇到这种数组有序查找的情况，第一反应就是二分查找
• 但是这个数字不是只出现一次的，那么重点就是来了，如何确保找到最开始出现的那个数字呢
• 只需要我们在找到这个数字的时候，再继续判断。
  • 比如找到最开始出现的数字，那么当我们找到了其中的一个数字的时候，我们不会立即放回，而是让right =mid-1，继续查找
  • 同理，查找最右边的数字，left=mid+1

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        int first = -1;
        int last = -1;

        while (left <= right) {
            int mid = (left + right) / 2;

            // 找到第一个等于 target
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1; //没办法确定是不是第一个，所以继续想左找
            }
            if (target < nums[mid]) {
                right = mid - 1;
            }
            if (target > nums[mid]) {
                left = mid + 1;
            }
        }

        // 最后一个
        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                last = middle;
                left = middle + 1; // 重点，同理向右找
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return new int[]{first,last};
    }
}

原文地址：https://blog.csdn.net/yun_shui_/article/details/144082965

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