最容易說的是堅持，最難做的也是堅持！
1.遞迴1.1基礎概念遞迴，是指在函式的定義中使用函式自身的方法。也就是說，遞迴演算法是一種直接或者間接呼叫自身函式或者方法的演算法。
本質：是一種迴圈，而且在迴圈中執行的就是呼叫自己，遞迴呼叫將每次返回的結果存在棧幀中
遞迴三要素
遞迴結束條件：必須要有結束，不結束就會OOM了函式的功能：函式實現功能，比如計算，列印函式的等價關係式：遞迴公式，一般是每次執行之間，或者與個數之間的邏輯關係1.2 經典案例之斐波拉契數列0、1、1、2、3、5、8、13、21、34、55..... ，從第3個數開始，每個數等於前面兩個數的和
公式：fun(n)=fun(n-1)+fun(n-2)
程式碼實現：
public class Fibonacci { public static int sum(int n){ if (n<=1) return n;//結束條件 return sum(n-1)+sum(n-2);//功能和關係式 } public static void main(String[] args) { System.out.println(sum(10)); //55 }}斐波那契數列 普通遞迴解法為 O(2^n).
優缺點
優點：程式碼簡單
缺點：佔用空間巨大，遞迴太深會導致OOM,大量重複計算
應用
遞迴作為基礎演算法，應用非常廣泛，比如在二分查詢、快速排序、歸併排序、樹的遍歷上都有使用遞迴，回溯演算法、分治演算法、動態規劃中也大量使用遞迴演算法實現。
2.二分查詢2.1 基礎概念二分查詢（Binary Search）演算法，也叫折半查詢演算法，二分查詢是針對有序資料集合的查詢演算法，如果是無序資料集合就遍歷查詢。
本質
二分查詢之所以快速，是因為它在匹配不成功的時候，每次都能排除剩餘元素中一半的元素。因此可能包含目標元素的有效範圍就收縮得很快，而不像順序查詢那樣，每次僅能排除一個元素。
2.2 小案例之查詢有序陣列某個數的下標注意前提是有序陣列
迴圈實現：
package com.david;public class HalfSearch { public static int binarySearch(int[] nums,int n){ int low=0;//低位索引 int high=nums.length-1;//高位索引 int mid=0;//中間位置 while (low<=high){ mid=(low+high); if (n==nums[mid]){ return mid; }else if (n<nums[mid]){ //在左側，高位往左移動 high=mid-1; }else if (n>nums[mid]){ //在右側，低位往右移動 low=mid+1; } } return -1; } public static void main(String[] args) { int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82}; System.out.println(binarySearch(nums,66));//7 }}遞迴實現：
package com.david;public class HalfSearch { public static int bSearch(int[] nums,int n){ return bSearchUnit(nums,0,nums.length-1,n); } private static int bSearchUnit(int[] nums, int low, int high, int n) { int mid=(low+high)/2; if (n==nums[mid]) { return mid; }else if (n>nums[mid]){ //右側，low右移 return bSearchUnit(nums,mid+1,high,n); }else if(n<nums[mid]){ //左側，high左移 return bSearchUnit(nums,low,mid-1,n); } return -1; } public static void main(String[] args) { int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82}; System.out.println(bSearch(nums,66));//7 }}一個有序陣列有一個數出現1次，其他數出現2次，找出出現一次的數比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出現1次的數是7
思路：二分法查詢
偶數位索引跟後面的比相同，奇數位索引跟前面的比相同 則說明前面的都是出現2次的偶數位索引跟前面的比相同，奇數位索引跟後面的比相同 則說明後面的都是出現2次的
package com.david;public class HalfDemo { public static int bSearch(int[] nums){ int low=0; int high=nums.length-1; int mid; while (low<=high){ mid=(low+high)/2; if (mid%2==0){ //偶數 if (nums[mid]==nums[mid+1]){ //偶數如果和後一位相等，說明前面都是成對出現的 low=mid+1; }else if (nums[mid]==nums[mid-1]){ //偶數如果和前一位相等，說明後面都是成對出現的 high=mid-1; }else{ return nums[mid]; } } else{ //奇數 if (nums[mid]==nums[mid+1]){ //奇數如果和後一位相等，說明後面都是成對出現的 high=mid-1; }else if (nums[mid]==nums[mid-1]){ //奇數如果和前一位相等，說明前面都是成對出現的 low=mid+1; }else{ return nums[mid]; } } } return -1; } public static void main(String[] args) { int[] nums={1,1,2,2,3,3,4,5,5,6,6}; int n = bSearch(nums); System.out.println("n = " + n);//4 }}時間複雜度 O(logn).
優缺點優點：速度快，不佔空間，不開闢新空間缺點：必須是有序的陣列，資料量太小沒有意義，但資料量也不能太大，因為陣列要佔用連續的空間
應用
有序的查詢基本都可以使用二分法。