牛客題霸 [在轉(zhuǎn)動過的有序數(shù)組中尋找目標(biāo)值] C++題解/答案

題目描述

給出一個轉(zhuǎn)動過的有序數(shù)組，你事先不知道該數(shù)組轉(zhuǎn)動了多少
(例如,0 1 2 4 5 6 7可能變?yōu)? 5 6 7 0 1 2).
在數(shù)組中搜索給出的目標(biāo)值，如果能在數(shù)組中找到，返回它的索引，否則返回-1。
假設(shè)數(shù)組中不存在重復(fù)項(xiàng)。

題解：

如果全是有序的很好做，就是二分模板
但是現(xiàn)在存在翻轉(zhuǎn)，也就是存在有序部分，也存在無序部分
我們只需要在二分模板中進(jìn)行判斷，如果左側(cè)有序，判斷目標(biāo)值是在有序部分還是無序部分，右側(cè)也是這樣
詳細(xì)看代碼

代碼：

class Solution { public:/*** * @param A int整型一維數(shù)組 * @param n int A數(shù)組長度* @param target int整型 * @return int整型*/int search(int* A, int n, int target) {// write code hereif(n==0)return -1;int l=0;int r=n-1;while(l<=r){int mid=l+((r-l)>>1);if(A[mid]==target)return mid;if(A[l]<A[mid]&&A[l]<=target&&A[mid]>target)r=mid-1;else if(A[mid]<A[r]&&!(A[mid]<target&&A[r]>=target))r=mid-1;else l=mid+1;}return -1;} };

總結(jié)

以上是生活随笔為你收集整理的牛客题霸 [在转动过的有序数组中寻找目标值] C++题解/答案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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