题目

题解

代码

public class code34 {
    // public static int[] searchRange(int[] nums, int target) {
    // int start = -1;
    // int end = -1;

    // for (int i = 0; i < nums.length; i++) {
    // if (nums[i] == target) {
    // start = i;
    // break;
    // }
    // }
    // for (int j = nums.length - 1; j >= 0; j--) {
    // if (nums[j] == target) {
    // end = j;
    // break;
    // }
    // }
    // int a[] = new int[] { start, end };
    // return a;
    // }

    public static int[] searchRange(int[] nums, int target) {
        int start = left_bound(nums, target);
        int end = right_bound(nums, target);
        int a[] = { start, end };
        return a;
    }

    public static int left_bound(int nums[], int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        // target 比所有数都大
        if (left == nums.length) {
            return -1;
        }
        return nums[left] == target ? left : -1;
    }

    public static int right_bound(int nums[], int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        // target 比所有数都小
        if (left == 0) {
            return -1;
        }
        return nums[left - 1] == target ? (left - 1) : -1;
    }

    public static void main(String[] args) {
        int nums[] = { 5, 7, 7, 8, 8, 10 };
        int target1 = 8;
        int target2 = 6;
        int index1[] = searchRange(nums, target1);
        int index2[] = searchRange(nums, target2);
        for (int i = 0; i < index1.length; i++) {
            System.out.print(index1[i] + " ");
        }
        System.out.println();
        for (int i = 0; i < index2.length; i++) {
            System.out.print(index2[i] + " ");
        }
        System.out.println();
    }
}
34. 在排序数组中查找元素的第一个和最后一个位置

题目

题解

代码

参考
