搜索范围 Leetcode – 查找排序数组中元素的第一个和最后一个位置

---

在本文中，我们将研究与搜索算法相关的编码面试中提出的一个有趣问题。问题是：Given a Sorted Array, we need to find the first and last position of an element in Sorted array。Search for a range这个问题在 Leetcode 上也被称为。我们将研究解决问题的不同方法及其实施，并分析我们方法的复杂性。

基本上，我们需要确定Array中重复键元素的第一次和最后一次出现。例如考虑这个数组：

具有重复元素的排序数组。

在这里，我们可以看到一个大小为 10 的数组，其中包含重复的元素 5 和 7。如果我们想知道元素 5 的第一次和最后一次出现，它将分别位于索引 3 和 4。类似地，对于元素 7，第一次和最后一次出现分别位于位置/索引 5 和 7。

Input: Array = {2,3,4,5,5,7,7,7,9,11}, target = 7
Output: 5,7                          // Comma separated Index of First and Last Occurrence.

Input: Array = {5,6,6,6,7,8,8,10}, target = 8
Output: 5,6

现在让我们看看我们解决这个问题的方法。

方法 1（使用线性搜索）

在此方法中，我们将遵循以下步骤：

• 首先，我们将从数组的开头或开始索引遍历数组。一旦我们得到目标元素，我们就存储它的索引。这将指示目标元素的第一个出现位置。然后，我们跳出循环并停止遍历。
• 现在，为了获取最后一个索引，我们将从数组的末尾索引开始遍历，一旦我们得到目标元素，我们就存储它的索引。这将指示元素的最后一次出现。然后，我们只需打印这些索引。

让我们看一下这个方法的代码：

import java.util.*;

public class Example
{

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
     // We initialize first and last as -1 if the target is not present in the array.
      int first = -1;
      int last = -1;

      for(int i=0;i<n;i++)
      {
          if(arr[i] == target)
          {
              first = i;
              break;
          }
      }

      for(int i=n-1;i>=0;i--)
      {
          if(arr[i] == target)
          {
              last = i;
              break;
          }
      }

      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{2,3,4,5,5,7,7,7,9,11};
   int n = arr.length;

   int target = 7;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 7 at index : 5 and the Last occurrence is at index : 7

Time Complexity:在这里，如果第一次出现在倒数第二个元素，我们执行线性搜索来获取索引，那么我们必须遍历整个数组。因此，整体运行时间为O(n).

方法 2（使用修改后的二分搜索优化）

这种方法的想法或目的是通过使用和修改二分搜索算法来最小化上述方法的运行时间。这种方法的分解如下所示：

• 基本上，我们实现了两个功能：
  1. findStartingIndex(Array,target)-> 获取目标元素的起始索引或第一次出现。
  2. findEndingIndex(Array,target)-> 获取目标元素的结束索引或最后一次出现。

• 现在，对于

  findStartingIndex()

  方法，我们将通过执行修改后的二进制搜索来搜索目标。我们计算

  mid = (low + high) / 2

  (low = 0 and high = Array_Size – 1)。随着数组的排序，对于 mid 的每个值，我们需要根据三个条件执行操作。

  1. If(Arr[mid] >= target)-> 这意味着如果索引中间的元素大于目标元素，那么为了更接近目标，我们需要更新high = mid - 1并在数组的左半部分进行搜索。如果元素等于目标，那么我们也需要更新高，这将确保我们尽可能接近目标的第一次出现。
  2. 如果第一个条件不成立，则意味着元素小于目标，因此我们更新low = mid + 1并将搜索扩展到数组的右半部分。
  3. If(Arr[mid] == target)-> 如果我们在索引 mid 处获得元素等于 target，我们将其索引存储为可能的解决方案并继续搜索直到 low<=high。

• 同样对于

  findEndingIndex()

  方法，我们通过进行一些更改来搜索目标。该算法与上面讨论的方法保持相同，只是需要更改条件。

  1. If(Arr[mid] <= target)-> 如果索引 mid 处的元素小于目标，那么为了更接近目标，我们更新 low = mid + 1，而不是 high 并继续在数组的右半边搜索。如果元素相等，那么我们也更新低并接近目标的最后一次出现。
  2. 如果第一个条件不成立，我们更新high = mid -1并在数组的左半部分搜索，因为中间的元素大于目标。
  3. If(Arr[mid] == target)-> 如果元素相等，我们存储它的索引并继续这些步骤直到low<=high.

让我们看一下上述方法的实现：

import java.util.*;

public class Example
{
  //finds Starting Index or First occurrence of target.
  static int findStartingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;

      while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]>=target)
      {
          high = mid-1;
      }
      // Condition 2 : When arr[mid] < target
      else
      {
          low = mid+1;
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  //finds Last occurrence of target.
  static int findEndingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;
           while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]<=target)
      {
          low = mid+1;
      }
      // Condition 2 : When arr[mid] > target
      else
      {
          high = mid-1;
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
      int first = findStartingIndex(arr,n,target);
      int last = findEndingIndex(arr,n,target);
      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{5,6,6,6,7,8,8,10};
   int n = arr.length;

   int target = 8;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 8 at index : 5 and the Last occurrence is at index : 6

时间复杂度：我们使用二分搜索来获取目标元素的第一次和最后一次出现。我们知道二分查找的运行时间为 O(log n)。此后，对 findStartingIndex() 和 findEndingIndex() 方法的调用分别花费 O(log n) 时间。因此，整体复杂度为 O(log n + log n) = O(log n)。这是解决此问题的最佳方法。

这就是搜索范围 Leetcode 的全部内容——在有序数组中查找元素的第一个和最后一个位置。

---

原文链接：https://codingdict.com/

---