欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Find First and Last Position of Element in Sorted Array

程序员文章站 2024-03-20 17:32:28
...

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

 /**
     * 从前往后找,从后往前找
     * @param nums
     * @param target
     * @return
     */
    public static int[] search1(int[] nums, int target)
    {
      int[] result = new int[]{-1,-1};
        if(nums == null || nums.length == 0) return result;
      for(int i = 0; i < nums.length; i++)
      {
          if(nums[i] == target)
          {
              result[0] = i;
              break;
          }
      }
      if(nums[0] == -1)
          return result;
      for(int i = nums.length-1; i>=0;i--)
      {
          if(nums[i] == target)
          {
              result[1] =i;
              break;
          }
      }
      return result;
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
   public  static int[] search2(int[] nums, int target)
   {
       int[] result = new int[]{-1,-1};
       if(nums == null || nums.length == 0) return result;
       int leftIndex = getIndex(nums,target,true);
       if(leftIndex == nums.length || nums[leftIndex] != target)
           return result;
       int rightIndex = getIndex(nums,target,false) - 1;
       result[0] = leftIndex;
       result[1] = rightIndex;
       return  result;
   }
   public static int getIndex(int[] nums, int target, boolean flag)
   {
       int lo = 0;
       int high = nums.length;
       while(lo < high)
       {
           int mid = (lo + high) / 2;
           if(nums[mid] > target || (flag && target == nums[mid]))
           {
               high = mid ;
           }
           else
           {
               lo = mid + 1;
           }
       }
       return  lo;
   }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
     public static int[] search3(int[] nums, int target)
     {
         int[] result = new int[]{-1,-1};
         if(nums == null || nums.length == 0) return result;
         result[0] = FindFirst(nums,target);
         result[1] = FindLast(nums,target);
         return result;
     }
    /**
     * 搜索左边第一个为target的元素
     * @param nums
     * @param target
     * @return
     */
   public static int FindFirst(int[] nums, int target)
   {
       int index = -1;
       int lo = 0;
       int hi = nums.length - 1;
       while(lo <= hi)
       {
           int mid = (lo + hi) / 2;
           if(nums[mid] >= target)
           {
               hi = mid - 1;
           }
           else
           {
               lo = mid + 1;
           }
           if(nums[mid] == target) index = mid;
       }
       return index;
   }

    /**
     * 寻找最后一个target的索引
     * @param nums
     * @param target
     * @return
     */
   public static int FindLast(int[] nums,int target)
   {
       int index = -1;
       int lo = 0;
       int hi = nums.length - 1;
       while(lo <= hi)
       {
           int mid = (lo + hi) / 2;
           if(nums[mid] <= target)
           {
               lo = mid +1;
           }
           else
           {
               hi = mid - 1;
           }
           if(nums[mid] == target) index = mid;
       }
       return index;
   }