Skip to content

Commit 6a11568

Browse files
feipxyzfeipxyz
committed
搜索旋转数组
1 parent 93d7b82 commit 6a11568

2 files changed

Lines changed: 70 additions & 16 deletions

File tree

‎Array/SearchInRotatedSortedArray.cpp‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
class Solution {
2+
public:
3+
int search(vector<int>& nums, int target) {
4+
int l = 0;
5+
int r = nums.size() - 1;
6+
while (l < r)
7+
{
8+
int m = (l + r) / 2;
9+
if (nums[m] == target)
10+
{
11+
return m;
12+
}
13+
else if (nums[l] < nums[r])
14+
{
15+
if (nums[m] < target)
16+
{
17+
l = m + 1;
18+
}
19+
else
20+
{
21+
r = m - 1;
22+
}
23+
}
24+
else
25+
{
26+
if (nums[m] >= nums[l])
27+
{
28+
if (nums[m] < target || nums[l] > target)
29+
{
30+
l = m + 1;
31+
}
32+
else
33+
{
34+
r = m - 1;
35+
}
36+
}
37+
else
38+
{
39+
if (nums[m] > target || target > nums[r])
40+
{
41+
r = m - 1;
42+
}
43+
else
44+
{
45+
l = m + 1;
46+
}
47+
}
48+
}
49+
}
50+
if (l == r && nums[l] == target) return l;
51+
return -1;
52+
}
53+
};

‎README.md‎

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -3,19 +3,19 @@
33
- 个人博客地址 [乡间小路](http://www.flyrie.top)
44

55
## 动态规划
6-
| OJ | # | Title | C++ Solution | Python Solution | Explanation | Importance Leval |
7-
| -------- | --- | -------------- | ------------------------------------------------------------------------------------------------------------------------------------- | --------------- | ------------------------------------------------------------------------------------- | ---------------- |
8-
| LeetCode | 10 | 正则表达式匹配 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/RegularExpressionMatching.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
9-
| LeetCode | 322 | 硬币兑换 | | | | |
10-
| LeetCode | 518 | 硬币兑换 II | | | | |
11-
| LeetCode | 32 | 最长有效括号 | | | | |
12-
| LintCode | 92 | 背包问题 | | | | |
13-
| LintCode | 125 | 背包问题 II | | | | |
14-
| LeetCode | 198 | 打家劫舍 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/HouseRobber.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
15-
| LeetCode | 174 | 地下城游戏 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/DungeonGame.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
16-
| LintCode | 515 | 房屋染色 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/PaintHouse.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
17-
| LintCode | 516 | 房屋染色 II | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/LongestSubstringWithoutRepeatingCharacters.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
18-
| LintCode | 32 | 最长有效括号 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/LongestValidParentheses.cpp) | | | |
6+
| OJ | # | Title | C++ Solution | Python Solution | Explanation | Importance Leval |
7+
| -------- | --- | -------------- | -------------------------------------------------------------------------------------------------------------------- | --------------- | ------------------------------------------------------------------------------------- | ---------------- |
8+
| LeetCode | 10 | 正则表达式匹配 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/RegularExpressionMatching.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
9+
| LeetCode | 322 | 硬币兑换 | | | | |
10+
| LeetCode | 518 | 硬币兑换 II | | | | |
11+
| LeetCode | 32 | 最长有效括号 | | | | |
12+
| LintCode | 92 | 背包问题 | | | | |
13+
| LintCode | 125 | 背包问题 II | | | | |
14+
| LeetCode | 198 | 打家劫舍 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/HouseRobber.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
15+
| LeetCode | 174 | 地下城游戏 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/DungeonGame.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
16+
| LintCode | 515 | 房屋染色 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/PaintHouse.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
17+
| LintCode | 516 | 房屋染色 II | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/PaintHouse2.cpp) | | [动态规划解题](http://flyrie.top/2018/08/15/Dynamic_Programming_Algorithm_Solutions/) | |
18+
| LintCode | 32 | 最长有效括号 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Dynamic%20Programming/LongestValidParentheses.cpp) | | | |
1919

2020
## 回溯法
2121
| OJ | # | Title | C++ Solution | Python Solution | Explanation |
@@ -66,6 +66,7 @@
6666
| LeetCode | 29 | 两数相除 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Bit%20Manipulation/DivideTwoIntegers.cpp) | | | important |
6767

6868
## 数组
69-
| OJ | # | Title | C++ Solution | Python Solution | Explanation | Importance Leval |
70-
| -------- | --- | ---------- | ------------------------------------------------------------------------------------------ | --------------- | ----------- | ---------------- |
71-
| LeetCode | 31 | 下一个排列 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Array/NextPermutation.cpp) | | | important |
69+
| OJ | # | Title | C++ Solution | Python Solution | Explanation | Importance Leval |
70+
| -------- | --- | ------------ | ----------------------------------------------------------------------------------------------------- | --------------- | ----------- | ---------------- |
71+
| LeetCode | 31 | 下一个排列 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Array/NextPermutation.cpp) | | | important |
72+
| LeetCode | 33 | 搜索旋转数组 | [C++](https://github.com/feipxyz/Algorithm-Solution/blob/master/Array/SearchInRotatedSortedArray.cpp) | | | important |

0 commit comments

Comments
 (0)