FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/PuzzleCoding/src/SearchInRotatedSortedArray.java at master · wodgithub/algorithm · GitHub
wodgithub
algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
SearchInRotatedSortedArray.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
88 lines (81 loc) · 3.18 KB
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
SearchInRotatedSortedArray.java
Copy path
File metadata and controls
88 lines (81 loc) · 3.18 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
/*
* Suppose a sorted array 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.
*
*/
public
class
SearchInRotatedSortedArray
{
public
static
void
main
(
String
[]
args
) {
int
[]
a
= {
2
,
3
,
2
,
2
,
2
,
2
,
2
,
2
,
2
,
2
};
System
.
out
.
println
(
searchInSortedArray
(
a
,
0
,
a
.
length
-
1
,
3
));
System
.
out
.
println
(
search
(
a
,
0
,
a
.
length
-
1
,
3
));
}
public
static
int
searchInSortedArray
(
int
[]
a
,
int
low
,
int
high
,
int
x
) {
if
(
low
>
high
||
low
<
0
||
high
>=
a
.
length
||
a
.
length
==
0
)
return
-
1
;
while
(
low
<=
high
) {
int
mid
= (
low
+
high
) /
2
;
if
(
x
<
a
[
mid
]) {
if
(
a
[
mid
] <
a
[
high
])
// the higher is ordered
high
=
mid
-
1
;
else
{
// the lower is ordered
if
(
x
<
a
[
low
])
// the higher is not ordered, x is less than all lowers.
low
=
mid
+
1
;
else
high
=
mid
-
1
;
}
}
else
if
(
x
>
a
[
mid
]) {
if
(
a
[
low
] <
a
[
mid
])
//the lower is ordered
low
=
mid
+
1
;
else
{
if
(
x
>
a
[
high
])
high
=
mid
-
1
;
else
low
=
mid
+
1
;
}
}
else
// x==a[mid]
return
mid
;
}
return
-
1
;
}
public
static
int
search
(
int
a
[],
int
left
,
int
right
,
int
x
) {
int
mid
= (
left
+
right
) /
2
;
if
(
x
==
a
[
mid
]) {
// Found element
return
mid
;
}
if
(
right
<
left
||
right
<
0
||
left
>=
a
.
length
||
a
.
length
==
0
) {
return
-
1
;
}
/* While there may be an inflection point due to the rotation, either the left or
* right half must be normally ordered. We can look at the normally ordered half
* to make a determination as to which half we should search.
*/
if
(
a
[
left
] <
a
[
mid
]) {
// Left is normally ordered.
if
(
x
>=
a
[
left
] &&
x
<=
a
[
mid
]) {
return
search
(
a
,
left
,
mid
-
1
,
x
);
}
else
{
return
search
(
a
,
mid
+
1
,
right
,
x
);
}
}
else
if
(
a
[
mid
] <
a
[
left
]) {
// Right is normally ordered.
if
(
x
>=
a
[
mid
] &&
x
<=
a
[
right
]) {
return
search
(
a
,
mid
+
1
,
right
,
x
);
}
else
{
return
search
(
a
,
left
,
mid
-
1
,
x
);
}
}
else
if
(
a
[
left
] ==
a
[
mid
]) {
// Left is either all repeats OR loops around (with the right half being all dups)
if
(
a
[
mid
] !=
a
[
right
]) {
// If right half is different, search there
return
search
(
a
,
mid
+
1
,
right
,
x
);
}
else
{
// Else, we have to search both halves
int
result
=
search
(
a
,
left
,
mid
-
1
,
x
);
if
(
result
== -
1
) {
return
search
(
a
,
mid
+
1
,
right
,
x
);
}
else
{
return
result
;
}
}
}
return
-
1
;
}
}
Back
|
FazBrowse Home
|
New Git URL