曲靖网站建设公司,上海做网站备案要多久,做网站的流程知乎,杭州 网站建站牛客题霸 [在转动过的有序数组中寻找目标值] C题解/答案
题目描述
给出一个转动过的有序数组#xff0c;你事先不知道该数组转动了多少 (例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2). 在数组中搜索给出的目标值#xff0c;如果能在数组中找到#xff0c;返回它的索引#…牛客题霸 [在转动过的有序数组中寻找目标值] C题解/答案
题目描述
给出一个转动过的有序数组你事先不知道该数组转动了多少 (例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2). 在数组中搜索给出的目标值如果能在数组中找到返回它的索引否则返回-1。 假设数组中不存在重复项。
题解
如果全是有序的很好做就是二分模板 但是现在存在翻转也就是存在有序部分也存在无序部分 我们只需要在二分模板中进行判断如果左侧有序判断目标值是在有序部分还是无序部分右侧也是这样 详细看代码
代码
class Solution {
public:/*** * param A int整型一维数组 * param n int A数组长度* param target int整型 * return int整型*/int search(int* A, int n, int target) {// write code hereif(n0)return -1;int l0;int rn-1;while(lr){int midl((r-l)1);if(A[mid]target)return mid;if(A[l]A[mid]A[l]targetA[mid]target)rmid-1;else if(A[mid]A[r]!(A[mid]targetA[r]target))rmid-1;else lmid1;}return -1;}
};
