二分查找的部分题目 · Sitrone/LeetcodeInJava@127bdae · GitHub
Skip to content

Commit 127bdae

Browse files
SitroneSitrone
committed
二分查找的部分题目
1 parent 209b806 commit 127bdae

7 files changed

Lines changed: 302 additions & 0 deletions

File tree

‎solutions/167. Two Sum II/TwoSum.java‎

Lines changed: 50 additions & 0 deletions

‎solutions/278. First Bad Version/FirstBadVersion.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package leetcode;
2+
3+
public class FirstBadVersion {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
}
9+
10+
public static boolean isBadVersion(int version){
11+
return false;
12+
}
13+
14+
// 最后退出循环时，h指向小于目标的点，l指向大于目标的点，这里第一个坏的version较大，所以返回l
15+
public static int firstBadVersion(int n) {
16+
int l = 1, h = n;
17+
while(l <= n){
18+
int mid = l + ((h - l) >> 1);
19+
if(isBadVersion(mid)){
20+
h = mid - 1;
21+
}else{
22+
l = mid + 1;
23+
}
24+
}
25+
return l;
26+
}
27+
}

‎solutions/34. Search for a Range/SearchRange.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package leetcode;
2+
3+
import java.util.Arrays;
4+
5+
public class SearchRange {
6+
7+
public static void main(String[] args) {
8+
// TODO Auto-generated method stub
9+
int[] nums = new int[]{1};
10+
System.out.println(Arrays.toString(searchRange(nums, 0)));
11+
}
12+
13+
public static int[] searchRange(int[] nums, int target) {
14+
if (nums == null || nums.length == 0) {
15+
return null;
16+
}
17+
18+
int[] result = new int[]{-1, -1};
19+
20+
int low = 0, high = nums.length - 1;
21+
int mid = 0;
22+
while(low <= high){
23+
mid = low + ((high - low) >> 1);
24+
if(target == nums[mid]){
25+
result[0] = mid;
26+
result[1] = mid;
27+
break;
28+
}else if(target > nums[mid]){
29+
low = mid + 1;
30+
}else{
31+
high = mid - 1;
32+
}
33+
}
34+
35+
// 先判断target存在不存在
36+
if(nums[mid] != target){
37+
return result;
38+
}
39+
40+
// 左边第二次二分搜索
41+
// 已经找到了目标元素，其中右边界已经确定
42+
// 所以判断条件是相等则向左看，否则大于则向右看
43+
int newLow = 0, newHigh = mid;
44+
while(newLow <= newHigh){
45+
int newMid = newLow + ((newHigh - newLow) >> 1);
46+
if(nums[newMid] == target){
47+
newHigh = newMid - 1;
48+
}else{
49+
newLow = newMid + 1;
50+
}
51+
}
52+
result[0] = newLow;
53+
54+
// 右边第三次二分搜索
55+
// 已经找到了目标元素，其中左边界已经确定
56+
// 所以判断条件是相等则向右看，大于则向左看
57+
newLow = mid; newHigh = nums.length - 1;
58+
while(newLow <= newHigh){
59+
int newMid = newLow + ((newHigh - newLow) >> 1);
60+
if(nums[newMid] == target){
61+
newLow = newMid + 1;
62+
}else{
63+
newHigh = newMid - 1;
64+
}
65+
}
66+
result[1] = newHigh;
67+
68+
return result;
69+
}
70+
}

‎solutions/35. Search Insert Position/SearchInsert.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package leetcode;
2+
3+
public class SearchInsert {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
int[] nums = new int[] { 1 };
8+
for (int i = 0; i < 3; i++) {
9+
System.out.print(i + " ");
10+
System.out.println(searchInsert1(nums, i));
11+
}
12+
}
13+
14+
/**
15+
* 直接搜索
16+
*
17+
* @param nums
18+
* @param target
19+
* @return
20+
*/
21+
public static int searchInsert(int[] nums, int target) {
22+
for (int i = 0; i < nums.length; i++) {
23+
if (target <= nums[i]) {
24+
return i;
25+
}
26+
}
27+
return nums.length;
28+
}
29+
30+
/**
31+
* 二分查找
32+
* 特点：对于数组中不存在的情况，最后总是：
33+
* low一定停在恰好比目标大的index上，high一定停在恰好比目标小的index上
34+
* 也即 num[high] target num[low]
35+
* 可视化操作：http://www.cs.usfca.edu/~galles/visualization/Search.html
36+
*/
37+
public static int searchInsert1(int[] nums, int target) {
38+
int low = 0, high = nums.length - 1;
39+
40+
while (low <= high) {
41+
int mid = low + ((high - low) >> 1);
42+
if (target == nums[mid]) {
43+
return mid;
44+
} else if (target > nums[mid]) {
45+
low = mid + 1;
46+
} else {
47+
high = mid - 1;
48+
}
49+
}
50+
51+
return low;
52+
}
53+
}

‎solutions/374. Guess Number Higher or Lower/GuessNumber_binarySearch.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package leetcode;
2+
3+
public class GuessNumber {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
}
9+
10+
// 典型的最基本的二分搜索
11+
public static int guessNumber(int n) {
12+
int l = 1, h = n;
13+
while(l <= h){
14+
int mid = l + ((h - l) >> 1);
15+
int g = guess(mid);
16+
if(g == 0){
17+
return mid;
18+
}else if(g == 1){
19+
l = mid + 1;
20+
}else{
21+
h = mid - 1;
22+
}
23+
}
24+
return -1;
25+
}
26+
}

‎solutions/413. Arithmetic Slices/NumberOfArithmeticSlices.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package leetcode;
2+
3+
public class NumberOfArithmeticSlices {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
int[] t = new int[]{1, 2, 3, 4, 5, 6};
9+
System.out.println(numberOfArithmeticSlices(t));
10+
}
11+
12+
/**
13+
* 找规律，a(3) = 1, a(4) = 3, a(5) = 6, a(6) = 10
14+
* a(3) - a(2) = 1 - 0 = 1
15+
* a(4) - a(3) = 3 - 1 = 2
16+
* a(5) - a(4) = 6 - 3 = 3
17+
* a(6) - a(5) = 10 - 6 = 4
18+
* 结果差成等差数列
19+
* @param A
20+
* @return
21+
*/
22+
public static int numberOfArithmeticSlices(int[] A) {
23+
int count = 0;
24+
int added = 0;
25+
26+
for (int i = 2; i < A.length; i++)
27+
if (A[i - 1] - A[i] == A[i - 2] - A[i - 1])
28+
count += ++added;
29+
else
30+
added = 0;
31+
32+
return count;
33+
}
34+
}

‎solutions/69. Sqrt(x)/MySqrt.java‎

Lines changed: 42 additions & 0 deletions

0 commit comments

Comments
 (0)