首页 > 文章列表 > 在一个已排序并旋转的数组中搜索元素的Java程序

在一个已排序并旋转的数组中搜索元素的Java程序

数组 搜索 旋转
111 2023-08-19

假设你有一个没有重复值的排序数组,并且从某个索引开始,这个数组被旋转了。你需要在其中搜索一个特定的元素。如果该元素在数组中存在,则返回其索引,否则返回-1。

在本文中,我们将使用两种方法(线性搜索和二分搜索)来解决给定的问题。

方法一:使用线性搜索

这种方法将按顺序搜索给定的元素。

算法

  • 步骤 1 - 首先,声明并初始化一个名为 'araylist' 的数组和一个名为 'searchElem' 的整数变量,我们将在数组中搜索该变量。我们还需要两个整数变量 'isFound' 和 'location'。

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

  • 步骤3 - 继续前进,我们创建一个if else块来检查变量'isFound'是否增加到1。如果它等于1,表示找到了元素,我们将返回索引。如果不是,则会执行else块中的语句。

Example 1

的中文翻译为:

示例 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

方法二:使用二分查找

这种方法将按照分而治之的规则来搜索给定的元素。

算法

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

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

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

  • 步骤 4 - 继续前进,我们创建一个 while 循环,该循环将从第一个索引运行到最后一个索引。在此循环中,我们声明一个整数变量 'mid' 来存储数组的中间索引。然后,我们创建一个 if 块,用于检查 'searchElem' 是否在中间索引处找到。如果找到了,则返回中间索引。

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

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

Example 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

结论

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