数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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”，以及两个参数“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”成为最后一个索引。
示例 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
结论
在本文中，我们讨论了两种在已排序并旋转的数组中搜索元素的方法。二分搜索方法比线性搜索更优化。它使用分治算法。
302 次浏览
