資料結構
網路
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 次瀏覽
