Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit81303ac

Browse files
author
piggy1991
committed
search
1 parent7b869d0 commit81303ac

File tree

2 files changed

+168
-1
lines changed

2 files changed

+168
-1
lines changed

‎array/SearchInRotatedSortedArray.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,4 +37,85 @@ public int search(int[] A, int target) {
3737

3838
return -1;
3939
}
40+
41+
// 2015.1.1 redo:
42+
publicintsearch1(int[]A,inttarget) {
43+
if (A ==null ||A.length ==0) {
44+
return -1;
45+
}
46+
47+
intl =0;
48+
intr =A.length -1;
49+
50+
while (l <r -1) {
51+
intmid =l + (r -l) /2;
52+
53+
if (A[mid] ==target) {
54+
returnmid;
55+
}
56+
57+
// left side is sorted.
58+
// BUG 1: if don't use >= , and use L < r in while loop, than there is some problem.
59+
if (A[mid] >A[l]) {
60+
if (target >A[mid] ||target <A[l]) {
61+
// move to right;
62+
l =mid +1;
63+
}else {
64+
r =mid -1;
65+
}
66+
}else {
67+
if (target <A[mid] ||target >A[r]) {
68+
// move to left;
69+
r =mid -1;
70+
}else {
71+
l =mid +1;
72+
}
73+
}
74+
}
75+
76+
if (A[l] ==target) {
77+
returnl;
78+
}elseif (A[r] ==target) {
79+
returnr;
80+
}
81+
82+
return -1;
83+
}
84+
85+
publicintsearch2(int[]A,inttarget) {
86+
if (A ==null ||A.length ==0) {
87+
return -1;
88+
}
89+
90+
intl =0;
91+
intr =A.length -1;
92+
93+
while (l <=r) {
94+
intmid =l + (r -l) /2;
95+
96+
if (A[mid] ==target) {
97+
returnmid;
98+
}
99+
100+
// left side is sorted.
101+
// BUG 1: if don't use >= , and use L < r in while loop, than there is some problem.
102+
if (A[mid] >=A[l]) {
103+
if (target >A[mid] ||target <A[l]) {
104+
// move to right;
105+
l =mid +1;
106+
}else {
107+
r =mid -1;
108+
}
109+
}else {
110+
if (target <A[mid] ||target >A[r]) {
111+
// move to left;
112+
r =mid -1;
113+
}else {
114+
l =mid +1;
115+
}
116+
}
117+
}
118+
119+
return -1;
120+
}
40121
}

‎array/SearchInRotatedSortedArray2.java

Lines changed: 87 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,92 @@ public boolean search(int[] A, int target) {
5555

5656
returnfalse;
5757
}
58-
58+
59+
/*
60+
* 2015.1.1 Redo:
61+
* */
62+
publicbooleansearch1(int[]A,inttarget) {
63+
if (A ==null ||A.length ==0) {
64+
returnfalse;
65+
}
66+
67+
intl =0;
68+
intr =A.length -1;
69+
70+
while (l <r -1) {
71+
intmid =l + (r -l) /2;
72+
73+
if (A[mid] ==target) {
74+
returntrue;
75+
}
76+
77+
// left sort
78+
if (A[mid] >A[l]) {
79+
// out of range.
80+
if (target >A[mid] ||target <A[l]) {
81+
l =mid +1;
82+
}else {
83+
r =mid -1;
84+
}
85+
// right sort.
86+
}elseif (A[mid] <A[l]) {
87+
// out of range.
88+
if (target <A[mid] ||target >A[r]) {
89+
r =mid -1;
90+
}else {
91+
l =mid +1;
92+
}
93+
}else {
94+
// move one node.
95+
l++;
96+
}
97+
}
98+
99+
if (A[l] ==target ||A[r] ==target) {
100+
returntrue;
101+
}
102+
103+
returnfalse;
104+
}
59105

106+
// Version 2:
107+
publicbooleansearch2(int[]A,inttarget) {
108+
if (A ==null ||A.length ==0) {
109+
returnfalse;
110+
}
111+
112+
intl =0;
113+
intr =A.length -1;
114+
115+
while (l <=r) {
116+
intmid =l + (r -l) /2;
117+
118+
if (A[mid] ==target) {
119+
returntrue;
120+
}
121+
122+
// left sort
123+
if (A[mid] >A[l]) {
124+
// out of range.
125+
if (target >A[mid] ||target <A[l]) {
126+
l =mid +1;
127+
}else {
128+
r =mid -1;
129+
}
130+
// right sort.
131+
}elseif (A[mid] <A[l]) {
132+
// out of range.
133+
if (target <A[mid] ||target >A[r]) {
134+
r =mid -1;
135+
}else {
136+
l =mid +1;
137+
}
138+
}else {
139+
// move one node.
140+
l++;
141+
}
142+
}
143+
144+
returnfalse;
145+
}
60146
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp