一.題目描寫敘述

二.解題技巧

因?yàn)檫@道題出現(xiàn)了旋轉(zhuǎn)的情況，即比第一個(gè)元素小的元素可能出如今數(shù)值的后半段或者不出現(xiàn)。

因此。能夠考慮採用變種的二分查找，即在比較中間元素與目標(biāo)之前，先比較第一個(gè)元素與目標(biāo)的關(guān)系。這個(gè)時(shí)候，會(huì)出現(xiàn)三種情況：

1.第一個(gè)元素剛好等于目標(biāo)，返回第一個(gè)元素的坐標(biāo)，函數(shù)結(jié)束；
2.第一個(gè)元素大于目標(biāo)。那么目標(biāo)就可能存在被旋轉(zhuǎn)到數(shù)組后面的情況，這個(gè)時(shí)候，還要比較與數(shù)組中間元素的關(guān)系，這個(gè)時(shí)候又會(huì)有三種情況：

a.中間元素大于第一個(gè)元素，這個(gè)時(shí)候。目標(biāo)可能存在于數(shù)組的后半段中，遞歸調(diào)用函數(shù)，尋找目標(biāo)的坐標(biāo)； b.中間元素等于目標(biāo)。返回中間元素的坐標(biāo)，函數(shù)結(jié)束； c.中間元素小于第一個(gè)元素。這個(gè)時(shí)候。又能夠分為兩種情況進(jìn)行：(1).中間元素小于目標(biāo)元素。那么目標(biāo)元素可能存在于數(shù)組的后半段中，遞歸調(diào)用函數(shù)，尋找目標(biāo)的坐標(biāo)；(2).中間元素大于目標(biāo)元素。那么目標(biāo)元素可能存在于數(shù)組的前半段中，遞歸調(diào)用函數(shù)。尋找目標(biāo)的坐標(biāo)；

3.第一個(gè)元素小于目標(biāo)，這是也有三種情況須要考慮：

a.中間元素等于目標(biāo)元素，返回中間元素的坐標(biāo)，函數(shù)結(jié)束； b.中間元素大于第一個(gè)元素，這個(gè)時(shí)候，也有兩種情況要考慮：(1).中間元素大于目標(biāo)，那么目標(biāo)元素可能存在于數(shù)組的前半段中，遞歸調(diào)用函數(shù)，尋找目標(biāo)的坐標(biāo)；(2).中間元素小于目標(biāo)，那么目標(biāo)元素可能存在于數(shù)組的后半段中，遞歸調(diào)用函數(shù)，尋找目標(biāo)的坐標(biāo)；c.中間元素小于第一個(gè)元素，那么目標(biāo)元素可能存在于數(shù)組的前半段中，遞歸調(diào)用函數(shù)，尋找目標(biāo)的坐標(biāo)；

當(dāng)然，還須要考慮數(shù)組的元素個(gè)數(shù)為0，1, 2,的情況，以及對(duì)于遞歸的過程中數(shù)組的起始位置坐標(biāo)以及數(shù)組中元素的個(gè)數(shù)。這些才是這道題的難點(diǎn)所在，我也是調(diào)試了非常久才調(diào)通代碼的。

三.演示樣例代碼

// 時(shí)間復(fù)雜度O(log n)。空間復(fù)雜度O(1) #include <iostream>using namespace std;class Solution { public:int SearchRotatedSortedArray(int A[], int n, int target){int start = 0;int end = n;int middle = start + (end - start) / 2;while (start != end){if (target == A[middle])return middle;if (A[start] < A[middle]){if ((target < A[middle]) && (A[start] <= target))end = middle;elsestart = middle + 1;}else{if ((target > A[middle]) && (target <= A[end - 1]))start = middle + 1;elseend = middle;}}return -1; // 在數(shù)組中找不到目標(biāo)元素時(shí)返回-1} };

四.體會(huì)

這答題的難點(diǎn)在于邊界條件和遞歸過程中的數(shù)組的第一個(gè)元素的指針設(shè)置和數(shù)組元素個(gè)數(shù)的設(shè)置上面，邊界條件常常是面試題考查的重點(diǎn)。

轉(zhuǎn)載于:https://www.cnblogs.com/gavanwanggw/p/7159502.html

總結(jié)

以上是生活随笔為你收集整理的leetcode笔记：Search in Rotated Sorted Array的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。