遞歸二分查找java

1. java基礎語法部分有哪些

Java的基礎語法包括：
1. 開發環境搭建
2. 常量
3. 變數
4. 數據類型
5. 運算符
6. 選擇結構-if-switch
7. 循環結構-while-【do-while】-for以及各種循環控制與多層嵌套循環
8. 方法的設計與使用
9. 數組
10. 遞歸
11. 冒泡-選擇等多種排序
12. 二分查找
13. 線性查找

2. java二分法查找的遞歸演算法怎麼實現

什麼是二分查找？

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

3. <演算法圖解>

二分查找、大O分析法；數組和鏈表；遞歸、快速排序；分治、動態規劃、貪婪演算法；散列表（鍵值對組成的數據結構）；圖演算法（模擬網路的方法）：廣度優先搜索、迪傑斯特拉演算法（計算網路中兩點之間最短距離）；K近鄰（KNN，用於創建推薦系統、OCR引擎、預測股價、物件分類）。

二分查找的時間復雜度為log2n，多少個2相乘等於n。

有序數組，定義low和high，非一個元素，猜中，大了，小了。

選擇排序：o(n方)，快速排序：o(nlogn)，存儲最小的值，存儲最小元素的索引，找出最小的值，加到新數組中。

循環，程序的性能更好，遞歸，程序更容易理解。棧有兩種操作：壓入和彈出。

每個遞歸函數都有兩部分：基線條件和遞歸條件，遞歸條件指的是函數調用自己，基線條件指的是函數不再調用自己，避免無限循環。

編程概念，調用棧，計算機在內部使用被稱為調用棧的棧，遞歸是調用自己的函數。

調用棧可能佔用大量內存，解決方案是編寫循環代碼，或者使用尾遞歸，但並非所有的語言都支持尾遞歸。

分治-遞歸式問題解決辦法：步驟：找出基線條件，確定如何縮小問題的規模，使其符合基線條件。

涉及數組的遞歸函數，基線條件通常是數組為空或只包含一個元素。

快速排序-D&C演算法：步驟：設置基線條件，數組小於2，選擇基準值，將數組分成兩個子數組：小於和大於基準值的元素，對這兩個子數組進行快速排序，遞歸調用。

合並排序：o(nlogn)，快速排序：o(nlogn)：層數o(logn)乘每層需要的時間o(n)，但最差情況為o(n方)。

散列表-基本數據結構之一：內部機制：實現、沖突、散列函數。

散列表無序，數據結構：數組、列表、（棧、不能用於查找）、散列表（包含額外邏輯）。

數組和鏈表都直接映射到內存，但散列表使用散列函數來確定元素存儲位置。

散列函數：不同的輸入映射到不同的索引，輸出不同的數字，散列表是散列函數和數組的結合，也稱散列映射、映射、字典、關聯數組。

緩存的數據存儲在散列表中，訪問頁面時，先檢查散列表是否存儲了頁面。

如果兩個鍵映射到了同一個位置引發沖突，可以在這個位置存儲一個鏈表，好的散列函數可以減少沖突。

填裝因子為散列表元素/位置總數，因子越低，發生沖突的可能性越小，性能越高。

廣度優先搜索（BFS）的含義：解決最短路徑問題的演算法。

步驟：使用圖來建立問題模型，使用廣度優先搜索演算法（是否有路徑，哪個路徑最短）。

所有演算法中，圖演算法是最有用的。

隊列（數據結構）：類似於棧，不能隨機訪問隊列中元素，只支持入隊和出隊（壓入和彈出），先加入的先出隊，即先進先出（FIFO），而棧是後進先出（LIFO）。

有向圖：關系是單向的，無向圖：沒有箭頭，直接相連的節點互為鄰居。

拓撲排序：根據圖創建一個有序列表。

迪傑斯特拉演算法：適用於加權圖（提高或降低某些邊的權重），找出加權圖中的最短路徑。

只適用於有向無環圖，如果有負權邊，不能使用迪傑斯特拉演算法，因為演算法假設處理過的節點，沒有前往終點的最短路徑，故，有負權邊的可用貝爾曼-福特演算法。

在未處理的節點找到開銷最小的節點，遍歷當前節點的所有鄰居，如果經當前節點前往該鄰居更近，就更新鄰居開銷，同時將該鄰居的父節點設置為當前節點，將當前節點標記為處理過，找出接下來要處理的節點，並循環。

貪婪演算法：每步都選擇局部最優解，最終就是全局最優解，易於實現，運行快，是個不錯的近似演算法。

集合類似於列表，但是不包含重復的元素。

貪婪演算法：o(n方)，NP完全問題：需要計算所有的解，從中選出最小距離，計算量大，最佳做法是使用近似演算法。

動態規劃：約定條件下找到最優解，在問題可分解為彼此獨立且離散的子問題時，就可使用動態規劃來解決。

動態規劃解決方案涉及網路，每個單元格都是子問題，需考慮如何將問題分解為子問題。

最長公共序列。

K最近鄰演算法（KNN）：電影推薦系統。

特徵抽取：指標打分，計算距離（相似程度），N維。

KNN的基本工作：分類和回歸。

應用：OCR光學字元識別（optical character recognition），提取線段、點、曲線特徵，找出與新圖像最近的鄰居；語音識別，人臉識別。

垃圾郵件過濾器：樸素貝葉斯分類器。

二叉查找樹（binary search tree）：有序樹狀數據結構。

二叉查找樹插入和刪除操作快於有序數組，但不能隨機訪問（沒有索引）。

紅黑樹是處於平衡狀態的特殊二叉樹，不平衡時，如向右傾斜時性能不佳。

B樹是一種特殊的二叉樹。

反向索引：一個散列表，將單詞映射到包含他的頁面，常用於創建搜索引擎。

並行演算法：速度的提升非線性，因為並行性管理開銷和負載均衡。

分布式演算法：特殊的並行演算法，maprece（映射和歸並函數），映射：任務多時自動分配多台計算機完成，將一個數組轉換成另一個數組，歸並是將一個數組轉換成一個元素。

線性規劃：在給定約束條件下最大限度的改善指定指標，使用simplex演算法，圖演算法為線性規劃子集。