Java 对于在排序和旋转数组中搜索元素

假设您有一个没有重复值的排序数组，并且从某个索引开始，该数组发生了旋转。您必须在其中搜索特定的元素。如果数组中存在该元素，则返回其索引，否则返回-1。

在本文中，我们将使用两种方法解决给定的问题，即线性搜索和二进制搜索。

方法1：使用线性搜索

该方法将以顺序的方式搜索给定元素。

步骤

• 步骤1 - 首先，声明并初始化一个名为’araylist’的数组和一个名为’searchElem’的整数变量，这是我们要在数组中搜索的元素。我们还需要两个整数变量’isFound’和’location’。

• 步骤2 - 现在，创建一个for循环，它将运行到数组的长度。在此循环中，使用一个if块来检查数组中是否存在’searchElem’。如果可用，将其索引存储在变量’location’中，并将变量’isFound’增加到1。

• 步骤3 - 接下来，我们创建一个if else块来检查变量’isFound’是否增加到1。如果等于1，表示找到了元素，并返回索引。如果不是，则执行else块中的语句。

示例1

public class Linear {
   public static void main(String[] args) {
      int araylist[] = {87, 89, 93, 0, 2, 5, 19};
      int searchElem = 2;
      int isFound = 0;
      int location = 0;
      for(int i = 0; i < araylist.length; i++) {
         if(searchElem == araylist[i]) {
            isFound = 1;
            location = i;
         } 
      }
      if(isFound == 1) {
         System.out.print("The given element is available at index: " + location);
      } else {
         System.out.print("Element is not available");
      }
   }
}

输出

The given element is available at index: 4

方法2：使用二分搜索

这种方法使用分而治之的规则来搜索给定的元素。

步骤

• 步骤1 - 首先，声明并初始化一个名为’araylist’的数组和一个名为’searchElem’的整数变量。我们将在数组中搜索’searchElem’。

• 步骤2 - 我们创建一个参数化方法，返回类型为int，命名为’bSearch’，并带有两个类型为int的参数’araylist[]’和’searchElem’。

• 步骤3 - 在方法’bSearch’中，我们将声明并初始化变量’l’，用于存储数组的第一个索引，以及’h’，用于存储数组的最后一个索引。

• 步骤4 - 接下来，我们创建一个while循环，它将从第一个索引运行到最后一个索引。在这个循环中，我们声明一个整数变量’mid’，用于存储数组的中间索引。然后，我们创建一个if块，用于检查’mid’索引是否找到了’searchElem’。如果找到了，将返回mid索引。

• 步骤5 - 现在，我们创建第二个if块，用于检查左侧数组是否已排序。如果已排序，则在下一个if块中再次检查’searchElem’是否在第一个索引和mid索引之间。如果在它们之间，则’mid-1’成为最后一个索引，否则’mid + 1’成为第一个索引。

• 步骤6 - 如果左侧数组未排序，那么意味着右侧数组已排序。因此，在else块中，我们创建另一个if块，用于检查’searchElem’是否在mid索引和最后一个索引之间。如果在它们之间，则’mid + 1’成为第一个索引，否则’mid-1’成为最后一个索引。

示例2

public class Binary {
   public int bSearch(int araylist[], int searchElem) {
      int l = 0;
      int h = araylist.length - 1;
      while(l <= h) {
         int mid = (l + h) / 2;
         if(araylist[mid] == searchElem) {
            return mid;
         }
         if(araylist[l] <= araylist[mid]) {
            if(searchElem >= araylist[l] && searchElem < araylist[mid]) {
               h = mid - 1;
            } else {
               l = mid + 1;
            } 
         } else {
            if(searchElem > araylist[mid] && searchElem <= araylist[h]) {
               l = mid + 1;
            } else {
               h = mid - 1;
            }
         }
      }
      return -1;
   }
   public static void main(String[] args) {
      int araylist[] = {87, 89, 93, 0, 2, 5, 19};
      int searchElem = 2;
      Binary obj = new Binary(); 
      // object creation 
      System.out.println("The given element is available at index: " + obj.bSearch(araylist, searchElem)); 
      // calling method with arguments
   }
}

输出

The given element is available at index: 4

结论

在本文中，我们讨论了在排序和旋转的数组中搜索元素的两种方法。二分查找方法比线性查找更优化，它使用分治算法。