33 搜索旋轉(zhuǎn)排序數(shù)組

LeetCode題目鏈接鏈接

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進(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):常量階寒瓦,運行時間為常量

(2)O(logn):對數(shù)階,如二分搜索算法

(3)O(n):線性階坪仇,如n個數(shù)內(nèi)找最大值

(4)O(nlogn):對數(shù)階杂腰,如快速排序算法

(5)O(n^2):平方階,如選擇排序椅文,冒泡排序

(6)O(n^3):立方階喂很,如兩個n階矩陣的乘法運算

(7)O(2^n):指數(shù)階皆刺,如n個元素集合的所有子集的算法

(8)O(n!):階乘階,如n個元素全部排列的算法


對于O(logn)羡蛾,可以參照下面的博客鏈接

[收藏]時間復(fù)雜度 O(log n) 意味著什么漓帅? - [| 小人物痴怨,大世界 - CSDN博客


分析:

其實這道理只要找對分類情況的話,就很簡單了腿箩。但是這個情況不好找。

由于數(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é)果

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末湿右,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子罚勾,更是在濱河造成了極大的恐慌毅人,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,817評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件尖殃,死亡現(xiàn)場離奇詭異丈莺,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)送丰,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,329評論 3 385
  • 文/潘曉璐 我一進(jìn)店門缔俄,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蚪战,你說我怎么就攤上這事牵现。” “怎么了邀桑?”我有些...
    開封第一講書人閱讀 157,354評論 0 348
  • 文/不壞的土叔 我叫張陵瞎疼,是天一觀的道長。 經(jīng)常有香客問我壁畸,道長贼急,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,498評論 1 284
  • 正文 為了忘掉前任捏萍,我火速辦了婚禮太抓,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘令杈。我一直安慰自己走敌,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 65,600評論 6 386
  • 文/花漫 我一把揭開白布逗噩。 她就那樣靜靜地躺著掉丽,像睡著了一般跌榔。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上捶障,一...
    開封第一講書人閱讀 49,829評論 1 290
  • 那天僧须,我揣著相機(jī)與錄音,去河邊找鬼项炼。 笑死担平,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的锭部。 我是一名探鬼主播,決...
    沈念sama閱讀 38,979評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼空另,長吁一口氣:“原來是場噩夢啊……” “哼蹋砚!你這毒婦竟也來了摄杂?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,722評論 0 266
  • 序言:老撾萬榮一對情侶失蹤墨坚,失蹤者是張志新(化名)和其女友劉穎泽篮,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體帽撑,經(jīng)...
    沈念sama閱讀 44,189評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡亏拉,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,519評論 2 327
  • 正文 我和宋清朗相戀三年及塘,在試婚紗的時候發(fā)現(xiàn)自己被綠了锐极。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,654評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡肋层,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出槽驶,到底是詐尸還是另有隱情,我是刑警寧澤掂铐,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布全陨,位于F島的核電站,受9級特大地震影響柿菩,放射性物質(zhì)發(fā)生泄漏雨涛。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,940評論 3 313
  • 文/蒙蒙 一凉泄、第九天 我趴在偏房一處隱蔽的房頂上張望蚯根。 院中可真熱鬧,春花似錦颅拦、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,762評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至登夫,卻和暖如春允趟,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,993評論 1 266
  • 我被黑心中介騙來泰國打工分唾, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留绽乔,地道東北人。 一個月前我還...
    沈念sama閱讀 46,382評論 2 360
  • 正文 我出身青樓折砸,卻偏偏與公主長得像睦授,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子去枷,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,543評論 2 349

推薦閱讀更多精彩內(nèi)容