java刷题[力扣34.在排序数组中查找元素的第一个和最后一个位置]

题目链接-->34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题目描述：

 题目思路：

1.。非递减顺序排列的整数数组（即 递增顺序但可能会有重复元素）

=》  思考用二分查找 来解决

2.。分别实现Leftmost 和Rightmost 两个方法

Leftmost（返回与目标相同的 重复元素里 最靠左边的，未找到 则返回-1）

Leftmost方法 代码实现：

  public int Leftmost(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        int candidate = -1;//将候选值 初始化为-1
        while (i <= j) {
            int mid = (i + j) >>> 1;
            
            if (target < a[mid]) {
                j = mid - 1;
            } else if (target > a[mid]) {
                i = mid + 1;
            } else {
//当找到目标值时，更新候选值，继续向左边找
                candidate = mid;
                j = mid - 1;
            }
        }
        return candidate;
//找到，则返回相同元素中最靠左的
//未找到，则返回 -1
    }

Rightmost同理；

题目完整代码实现：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int x = Leftmost(nums, target);
        if (x == -1) { //未找到，直接返回[-1,-1]
            return new int[] { -1, -1 };
        } else {
            return new int[] { x, Rightmost(nums, target) };
        }
    }

    public int Leftmost(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            
            if (target < a[mid]) {
                j = mid - 1;
            } else if (target > a[mid]) {
                i = mid + 1;
            } else {
                candidate = mid;
                j = mid - 1;
            }
        }
        return candidate;
    }

    public int Rightmost(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
           
            if (target > a[mid]) {
                i = mid + 1;
            } else if (target < a[mid]) {
                j = mid - 1;
            } else {
                candidate = mid;
                i = mid + 1;
            }
        }
        return candidate;
    }
}