Skip to content

Commit a98ae0c

Browse files
znn0301znn0301
committed
二分查找及其变种
1 parent 2fc6fdc commit a98ae0c

File tree

2 files changed

+201
-0
lines changed

2 files changed

+201
-0
lines changed

‎src/main/java/com/chen/algorithm/study/test240/Solution.java

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,10 @@ public class Solution {
2121
*/
2222
public boolean searchMatrix(int[][] matrix, int target) {
2323

24+
if (matrix == null) {
25+
return false;
26+
}
27+
2428
int rows = matrix.length;
2529
if (rows == 0) {
2630
return false;

‎src/main/java/com/chen/algorithm/study/test704/Solution.java

Lines changed: 197 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,197 @@
1+
package com.chen.algorithm.study.test704;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/10/9 15:31
6+
* @Description: 二分查找 https://blog.csdn.net/Lngxling/article/details/78217619
7+
*/
8+
public class Solution {
9+
10+
/**
11+
* 适用于升序数组，可做相应调整适用降序数组
12+
*/
13+
public static int bsearch(int[] array, int target) {
14+
if (array == null || array.length == 0
15+
/*|| target < array[0] || target > array[array.length - 1]*/) {
16+
return -1;
17+
}
18+
19+
int left = 0;
20+
int right = array.length - 1;
21+
//这里必须是 >=,切记遗漏 =
22+
while (right >= left) {
23+
// 当start=Integer.MAX_VALUE时，给它加个1都会溢出。安全的写法是：mid = start + (end-start)/2,但是会造成死循环，弃用
24+
//int mid = min + (max - min) >> 1;
25+
int mid = (left + right) >> 1;
26+
if (target == array[mid]) {
27+
return mid;
28+
}
29+
if (target < array[mid]) {
30+
right = mid - 1;
31+
}
32+
if (target > array[mid]) {
33+
left = mid + 1;
34+
}
35+
}
36+
return -1;
37+
}
38+
39+
/**
40+
* 查找第一个与target相等的元素
41+
* 当key=array[mid]时， 往左边一个一个逼近，right = mid -1; 返回left
42+
*/
43+
public static int bsearch1(int[] array, int target) {
44+
if (array == null || array.length == 0
45+
/*|| target < array[0] || target > array[array.length - 1]*/) {
46+
return -1;
47+
}
48+
int left = 0;
49+
int right = array.length - 1;
50+
while (right >= left) {
51+
int mid = (left + right) >> 1;
52+
if (array[mid] >= target) {
53+
right = mid - 1;
54+
} else {
55+
left = mid + 1;
56+
}
57+
}
58+
59+
if (left < array.length && array[left] == target) {
60+
return left;
61+
}
62+
return -1;
63+
64+
}
65+
66+
/**
67+
* 查找最后一个与target相等的元素
68+
* 当key=array[mid]时， 往右边一个一个逼近，left = mid + 1; 返回right
69+
*
70+
* @return
71+
*/
72+
public static int bsearch2(int[] array, int target) {
73+
if (array == null || array.length == 0 /*|| target < array[0] || target > array[array.length - 1]*/) {
74+
return -1;
75+
}
76+
int left = 0;
77+
int right = array.length - 1;
78+
while (right >= left) {
79+
int mid = (left + right) >> 1;
80+
if (array[mid] <= target) {
81+
left = mid + 1;
82+
} else {
83+
right = mid - 1;
84+
}
85+
}
86+
87+
if (right >= 0 && array[right] == target) {
88+
return right;
89+
}
90+
return -1;
91+
}
92+
93+
// 二分查找变种说明
94+
//public void test(int[] array, int target){
95+
//
96+
// int left = 0;
97+
// int right = array.length - 1;
98+
// // 这里必须是 <=
99+
// while (left <= right) {
100+
// int mid = (left + right) / 2;
101+
// if (array[mid] ? key) {
102+
// //... right = mid - 1;
103+
// }
104+
// else {
105+
// // ... left = mid + 1;
106+
// }
107+
// }
108+
// return xxx;
109+
//}
110+
111+
112+
/**
113+
* 查找第一个等于或者大于key的元素
114+
*/
115+
public static int bsearch3(int[] array, int target) {
116+
if (array == null || array.length == 0) {
117+
return -1;
118+
}
119+
int left = 0;
120+
int right = array.length - 1;
121+
while (right >= left) {
122+
int mid = (left + right) >> 1;
123+
if (array[mid] >= target) {
124+
right = mid - 1;
125+
} else {
126+
left = mid + 1;
127+
}
128+
}
129+
return left;
130+
}
131+
132+
/**
133+
* 查找第一个大于key的元素
134+
*/
135+
public static int bsearch4(int[] array, int target) {
136+
if (array == null || array.length == 0) {
137+
return -1;
138+
}
139+
int left = 0;
140+
int right = array.length - 1;
141+
while (right >= left) {
142+
int mid = (left + right) >> 1;
143+
if (array[mid] > target) {
144+
right = mid - 1;
145+
} else {
146+
left = mid + 1;
147+
}
148+
}
149+
return left;
150+
}
151+
152+
/**
153+
* 查找最后一个等于或者小于key的元素
154+
*/
155+
public static int bsearch5(int[] array, int target) {
156+
if (array == null || array.length == 0) {
157+
return -1;
158+
}
159+
int left = 0;
160+
int right = array.length - 1;
161+
while (right >= left) {
162+
int mid = (left + right) >> 1;
163+
if (array[mid] <= target) {
164+
left = mid + 1;
165+
} else {
166+
right = mid - 1;
167+
}
168+
}
169+
return right;
170+
}
171+
172+
/**
173+
* 查找最后一个小于key的元素
174+
*/
175+
public static int bsearch6(int[] array, int target) {
176+
if (array == null || array.length == 0) {
177+
return -1;
178+
}
179+
int left = 0;
180+
int right = array.length - 1;
181+
while (right >= left) {
182+
int mid = (left + right) >> 1;
183+
if (array[mid] < target) {
184+
left = mid + 1;
185+
} else {
186+
right = mid - 1;
187+
}
188+
}
189+
return right;
190+
}
191+
192+
public static void main(String[] args) {
193+
int[] array = {1, 1, 3, 6, 6, 6, 7, 9, 17, 17};
194+
int index = bsearch6(array, 0);
195+
System.out.println(index);
196+
}
197+
}

0 commit comments

Comments
 (0)