旋轉數組最小數字 矩陣中路徑c++

旋轉數組最小數字
一個數組最開始的若干個元素搬到數組的末尾，我們稱之爲數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}爲{1,2,3,4,5}的一個旋轉，該數組的最小值爲1。

首先能想到的就是順序遍歷，數組中最小的元素即爲整個旋轉數組的最小元素，但算法時間複雜度爲O(n)；

由旋轉數組的特性，因爲經排序好的數組旋轉得到的，所以由其特性可以知道，除了不旋轉的情況（即原數組），旋轉數組可以劃分爲兩個排序的子數組，前面的子數組元素均大於後面的子數組元素，存在分界線，所以可以想到的就是利用二分查找法，實現時間複雜度爲O(logn)；

注意考慮以下幾種情況的處理：
1）數組元素爲空的情況，（判斷，直接返回0）；
2）數組元素只有一個的情況，（判斷，直接返回該元素）；
3）數組旋轉0個元素，也就是沒有旋轉的情況，（最後返回mid對應的值，所以初始時令mid=low，遇到該情況while條件不成立，依然返回mid對應的值

矩陣中路徑

是一個可以用回朔法解決的典型題。
//1. 首先，在矩陣中任選一個格子作爲路徑的起點。如果路徑上的第i個字符不是ch，那麼這個格子不可能處在路徑上的第i個位置。如果路徑上的第i個字符正好是ch，那麼往相鄰的格子尋找路徑上的第i+1個字符。除在矩陣邊界上的格子之外，其他格子都有4個相鄰的格子。重複這個過程直到路徑上的所有字符都在矩陣中找到相應的位置。
//2. 由於回朔法的遞歸特性，路徑可以被開成一個棧。當在矩陣中定位了路徑中前n個字符的位置之後，在與第n個字符對應的格子的周圍都沒有找到第n+1個字符，這個時候只要在路徑上回到第n-1個字符，重新定位第n個字符。
//3. 由於路徑不能重複進入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來標識路徑是否已經進入每個格子。 當矩陣中座標爲（row,col）的格子和路徑字符串中相應的字符一樣時，從4個相鄰的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路徑字符串中下一個字符
//4. 如果4個相鄰的格子都沒有匹配字符串中下一個的字符，表明當前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個，然後重新定位。
//5. 一直重複這個過程，直到路徑字符串上所有字符都在矩陣中找到合適的位置