-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0033.c
132 lines (125 loc) · 3.21 KB
/
q0033.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//
// q0033.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0033.h"
#include "../common.h"
//33. Search in Rotated Sorted Array
//Medium
//1720
//259
//
//
//Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
//
//(i.e., [0,1,2,4,5,6,7] might become [4,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.
//
//Your algorithm's runtime complexity must be in the order of O(log n).
//
//Example 1:
//
//Input: nums = [4,5,6,7,0,1,2], target = 0
//Output: 4
//Example 2:
//
//Input: nums = [4,5,6,7,0,1,2], target = 3
//Output: -1
//Accepted
//334,539
//Submissions
//1,034,910
int search(int* nums, int numsSize, int target) {
int result = -1;
if (numsSize <= 0) {
return result;
}
int pLeft = 0;
int pRight= numsSize - 1;
int pMiddle = (pLeft + pRight) / 2;
if (nums[pRight] == target) {
return pRight;
}
while (pLeft < pRight) {
pMiddle = (pLeft + pRight) / 2;
// on the same side
if ((nums[pMiddle] >= nums[0]) == (target >= nums[0])) {
if (nums[pMiddle] == target) {
return pMiddle;
}else if (nums[pMiddle] > target){
pRight = pMiddle;
}else{
pLeft = pMiddle + 1;
}
}else if (nums[pMiddle] >= nums[0]){
pLeft = pMiddle + 1;
}else{
pRight = pMiddle;
}
}
return result;
}
//deprecated
//int search(int* nums, int numsSize, int target) {
// if (numsSize <= 0) {
// return -1;
// }
// int pLeft = 0;
// int pRight = numsSize - 1;
// if (nums[pLeft] == target) {
// return pLeft;
// }
// if (nums[pRight] == target) {
// return pRight;
// }
// int pMiddle = 0;
// while (pLeft < pRight) {
// pMiddle = (pLeft + pRight + 1) / 2;
// if (nums[pMiddle] == target) {
// return pMiddle;
// }
// if (pMiddle == pLeft || pMiddle == pRight) {
// return -1;
// }
// if (nums[pMiddle] > target){
// if (nums[pLeft] > target) {
// if (nums[pMiddle] > nums[pLeft]) {
// pLeft = pMiddle;
// }else{
// pRight = pMiddle;
// }
// }else{
// pRight = pMiddle;
// }
// }else{
// if (nums[pRight] < target) {
// if (nums[pMiddle] < nums[pRight]) {
// pRight = pMiddle;
// }else{
// pLeft = pMiddle;
// }
// }else{
// pLeft = pMiddle;
// }
// }
// }
// return -1;
//}
int question33(){
int numsSize = 7;
int nums[7] = {4,5,6,7,0,1,2};
// srand((int) time(0));
// int randomNumber = rand() % numsSize;
for (int i = 0; i < numsSize; i++) {
// nums[i] = (i + randomNumber) % (numsSize + 1);
printf(" %d",nums[i]);
}
printf("\n searchResult: index(%d)",search(nums, numsSize, 0));
return 0;
}