LeetCode題目鏈接鏈接
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組[0,1,2,4,5,6,7]可能變?yōu)閇4,5,6,7,0,1,2])。
搜索一個給定的目標(biāo)值，如果數(shù)組中存在這個目標(biāo)值，則返回它的索引，否則返回-1。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時間復(fù)雜度必須是O(logn) 級別。
示例 1:
輸入:nums = [4,5,6,7,0,1,2], target = 0輸出:4
示例?2:
輸入:nums = [4,5,6,7,0,1,2], target = 3輸出:-1
在做這道題之前。把時間復(fù)雜度重新理解一下
（1）O(1)：常量階，運(yùn)行時間為常量
（2）O(logn)：對數(shù)階，如二分搜索算法
（3）O(n)：線性階，如n個數(shù)內(nèi)找最大值
（4）O(nlogn)：對數(shù)階，如快速排序算法
（5）O(n^2)：平方階，如選擇排序，冒泡排序
（6）O(n^3)：立方階，如兩個n階矩陣的乘法運(yùn)算
（7）O(2^n)：指數(shù)階，如n個元素集合的所有子集的算法
（8）O(n!)：階乘階，如n個元素全部排列的算法
對于O(logn)，可以參照下面的博客鏈接
[收藏]時間復(fù)雜度 O(log n) 意味著什么？ - [| 小人物，大世界 - CSDN博客
分析：
其實(shí)這道理只要找對分類情況的話，就很簡單了。但是這個情況不好找。
由于數(shù)字無論這么翻轉(zhuǎn)，總有一個是正序的。另外一個是亂序或者。那么如何判斷是在正序或者亂序呢？整體思路是采用二分法，但是要修改二分法。
二分法?
int binarysearch(int arr[],int key,int left,int right) {
//求中間元素的下標(biāo)
? ? int mid = (left + right) /2;
//數(shù)組內(nèi)不含有指定元素，依據(jù)下標(biāo)的規(guī)則，退出
? ? if (left > right)
return -1;
//查找到指定元素
? ? if (key == arr[mid]) {
return mid;
//當(dāng)查找的元素大于中間下標(biāo)的元素，則改變開始下標(biāo)的位置
? ? }
else if (key > arr[mid]) {
return binarysearch(arr, key, mid +1, right);
}
else {
//當(dāng)查找的元素小于中間下標(biāo)的元素，則改變結(jié)束下標(biāo)的位置
? ? ? ? return binarysearch(arr, key, left, mid -1);
}
}
1. 如果第一位first < mid（first為要尋找的區(qū)間的第一位，mid為要尋找區(qū)間的中間位），
? ? ? ? 如果? first < target < array[mid]? 則該區(qū)間是正序
? ? ? ? 否則? target不在正序區(qū)間
2. 如果第一位first > mid
????如果? first < target < array[mid]?則該區(qū)間是正序
????否則? target不在正序區(qū)間
代碼
class Solution {
? ? public int search(int[] nums, int target) {
? ? ? ? if(nums.length<=0){
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? int first = nums[0];
? ? ? ? if(first == target){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? int last = nums[nums.length-1];
? ? ? ? if(last == target){
? ? ? ? ? ? return nums.length-1;
? ? ? ? }
? ? ? ? return binarysearch(nums, 0, nums.length-1,target,first, last);
? ? }
? ? public static int binarysearch(int array[], int low, int high, int target,int first,int last) {
? ? ? ? if (low > high) {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? if (low == high){
? ? ? ? ? ? if (array[low] == target){
? ? ? ? ? ? ? ? return low;
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? return -1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int mid = low + (high - low) / 2;
? ? ? ? if (target == array[mid]){
? ? ? ? ? ? return mid;
? ? ? ? }
? ? ? ? if (first < array[mid]){
? ? ? ? ? ? if (target > first && target < array[mid]){
? ? ? ? ? ? ? ? if (array[mid-1]==target){
? ? ? ? ? ? ? ? ? ? return mid-1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return binarysearch(array, low, mid-1, target, first,array[mid-1]);
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? if (array[mid+1]==target){
? ? ? ? ? ? ? ? ? ? return mid+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return binarysearch(array, mid + 1, high, target, array[mid+1], last);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (first > array[mid]? ){
? ? ? ? ? ? if (target > array[mid] && target < last){
? ? ? ? ? ? ? ? if (array[mid+1]==target){
? ? ? ? ? ? ? ? ? ? return mid+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return binarysearch(array, mid + 1, high, target,array[mid+1], last);
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? if (array[mid-1]==target){
? ? ? ? ? ? ? ? ? ? return mid-1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return binarysearch(array, low, mid - 1, target,first, array[mid - 1]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }
}
結(jié)果
