【题目】
Search in Rotated Sorted Array
Total Accepted:5827Total
Submissions:20925My Submissions
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7
might
become4 5 6 7 0 1 2
).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
【分析】
循环递增数组有这么一个性质:以数组中间元素将循环递增数组划分为两部分,则一部分为一个严格递增数组,而另一部分为一个更小的循环递增数组。
当中间元素大于首元素时,前半部分为严格递增数组,后半部分为循环递增数组;当中间元素小于首元素时,前半部分为循环递增数组;后半部分为严格递增数组。
【代码】
/*********************************
* 日期:2014-01-15
* 作者:SJF0115
* 题号: 33.Search in Rotated Sorted Array
* 来源:http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
class Solution {
public:
//二分查找
int search(int A[], int n, int target) {
int start = 0,end = n-1;
int mid;
while(start <= end){
mid = (start + end) / 2;
if(A[mid] == target){
return mid;
}
//中间元素大于最左边元素则左部分为有序数组
else if(A[mid] >= A[start]){
//目标位于左部分
if(target >= A[start] && target <= A[mid]){
end = mid - 1;
}
//目标位于右部分
else{
start = mid + 1;
}
}
//中间元素小于最右边元素则右部分为有序数组
else{
//目标位于右部分
if(target <= A[end] && target >= A[mid]){
start = mid + 1;
}
//目标位于左部分
else{
end = mid - 1;
}
}
}
return -1;
}
};
int main() {
int result;
Solution solution;
int A[] = {3,1};
result = solution.search(A,2,1);
printf("Result:%d\n",result);
return 0;
}
【分析二】
对于一个数组4,5,6,7,0,1,2 你首先找到那个转折点,就是大于下一个相邻数字的那个数字的下标,在这个数组就是数字7的下标3。
步骤:
1 找到转折点下标,把数组分成两个有序的子数组
2 如果转折点下标返回-1,意思是数组有序,可以直接在整个数组中查找
3返回不是-1,数组是旋转后的数组。 如果target大于等于第一个元素即A[0],那就在左半部分数组中查找,如果target小于A[0],那就在右半部分中寻找
【代码二】
/*********************************
* 日期:2015-01-04
* 作者:SJF0115
* 题目: 33.Search in Rotated Sorted Array
* 来源:https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
using namespace std;
class Solution {
public:
int search(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
// 旋转转折点
int pivot = FindPivot(A,n);
// 数组有序
if(pivot == -1){
return search(A,0,n-1,target);
}//if
if(A[pivot] == target){
return pivot;
}//if
// 数组旋转
// 在左半部分寻找
if(A[0] <= target){
return search(A,0,pivot,target);
}//if
// 在右半部分寻找
else{
return search(A,pivot+1,n-1,target);
}//else
}
private:
int search(int A[], int start,int end, int target) {
if(start > end){
return -1;
}
// 二分查找
while(start <= end){
// 中间节点
int mid = (start + end) / 2;
// 找到
if(A[mid] == target){
return mid;
}//if
// 左半部分
else if(A[mid] > target){
end = mid - 1;
}//else
// 右半部分
else{
start = mid + 1;
}//else
}//while
return -1;
}
// 寻找转折点
int FindPivot(int A[],int n){
int start = 0,end = n - 1;
// 数组有序
if(A[end] > A[start]){
return -1;
}//if
// 数组旋转
// 二分查找
while(start <= end){
int mid = (start + end) / 2;
// 转折点在[mid,end]区间中
if(A[mid] > A[start]){
start = mid;
}//if
// 转折点在[start,mid]区间中
else if(A[mid] < A[start]){
end = mid;
}//else
else{
return mid;
}
}//while
}
};
int main() {
Solution solution;
int A[] = {4,5,6,7,0,1,2};
//int A[] = {3,1};
cout<<solution.search(A,7,0)<<endl;
}
分享到:
相关推荐
Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值...
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E)...
Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. ...
leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步leetcode新题情况 blog_solution_...
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...
Search in Rotated Sorted Array74. Search a 2D Matrix I240. Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree Inorder Traversal144. Binary ...
leetcode添加元素使和等于 leetcode_py Python version of leetcode problems 33 Search in Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 target、num[0]、...
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
Search in Rotated Sorted Array II Search a 2D Matrix Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举...
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
简单编程: (分析,控制语句)排序 & 查找:二分查找:二分查找进阶:二分查找应用:二分查找应用:二分查找变种:二分查找变种:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/简单数学:...
leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
leetcode切割分组 leetcode 加减乘除运算 ...033_search_in_rotated_sorted_array.py # 旋转排序的数列中查找 034_find_first_and_last_position_of_element_in_sorted_array.py # 查找第一次出现和
in Rotated Sorted Array II/Solution.java) 2014/10/20 难的 [Java](./src/在旋转排序数组中查找最小值/Solution.java) 2014/10/15 中等的 [Java](./src/最大乘积子阵列/Solution.java) 2014/9/23 中等的 [Java](./...
search-in-rotated-sorted-array ,比较中间值和边,而不是目标和边 40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符