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("给定元素在索引处可用:" + location);
} else {
System.out.print("元素不可用");
}
}
}
输出
给定元素位于索引:4
方法 2:使用二分搜索
此方法将通过分而治之规则搜索给定元素。
算法
步骤 1 − 首先，声明并初始化一个名为"araylist"的数组和一个名为"searchElem"的整数变量。我们将在数组中搜索"searchElem"。
步骤 2 - 我们创建一个名为"bSearch"的返回类型为 int 的参数化方法，以及两个类型为 int 的参数"araylist[]"和"searchElem"。
步骤 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"将成为最后一个索引。
示例 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();
// 对象创建
System.out.println("给定元素在索引处可用:" + obj.bSearch(araylist, searchElem));
// 使用参数调用方法
}
}
输出
给定元素位于索引:4
结论
在本文中，我们讨论了在排序和旋转数组中搜索元素的两种方法。二分搜索方法比线性搜索更优化。它使用分而治之算法。
