题干

LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
image.png

讲解

排序数组找一个值，自然而然就能想到二分查找；当然如果是直接循环也没问题，只不过时间复杂度是O(n)，不符合题干要求；
题干中我们可以看到他要求O(log n)的时间复杂度，所以用的方法就是二分查找；

这里分享一下y总的整数二分查找的模板
image.png
注意第二种方法是 (l+r+1)/2

题解

  1. public static int[] searchRange(int[] nums, int target) {
  2.     if(nums.length == 0){
  3.         return new int[]{-1,-1};
  4.     }
  5.     int left = check_left(nums, target);
  6.     int right = check_right(nums, target);
  8.     if(nums[left] != target){
  9.         return new int[]{-1, -1};
  10.     }else{
  11.         return new int[]{left, right};
  12.     }
  14. }
  16. /**
  17.  * 查找第一个出现的位置
  18.  * @param nums
  19.  * @param target
  20.  * @return
  21.  */
  22. public static int check_left(int[] nums, int target){
  24.     int left = 0;
  25.     int right = nums.length-1;
  27.     while(left < right){
  28.         int temp = (left+right)/2;
  29.         if(nums[temp]>=target){
  30.             right = temp;
  31.         }else{
  32.             left = temp+1;
  33.         }
  34.     }
  36.     return left;
  37. }
  39. /**
  40.  * 查找最后一个出现的位置
  41.  * @param nums
  42.  * @param target
  43.  * @return
  44.   */
  45. public static int check_right(int[] nums, int target){
  47.     int left = 0;
  48.     int right = nums.length-1;
  50.     while(left < right){
  51.         int temp = (left+right+1)/2;
  52.         if(nums[temp]<=target){
  53.             left = temp;
  54.         }else{
  55.             right = temp-1;
  56.         }
  57.     }
  59.     return left;
  60. }