Skip to content

Commit d10b9b7

Browse files
chefyuanchefyuan
committed
Merge branch 'main' of github.com:chefyuan/algorithm-base
2 parents a5a0618 + 56c7755 commit d10b9b7

8 files changed

+181
-236
lines changed

‎animation-simulation/二分查找及其变种/leetcode 81不完全有序查找目标元素(包含重复值) .md

Lines changed: 3 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -40,10 +40,12 @@
4040

4141
#### **题目代码**
4242

43+
Java Code:
44+
4345
```java
4446
class Solution {
4547
public boolean search(int[] nums, int target) {
46-
int left = 0;
48+
int left = 0;
4749
int right = nums.length - 1;
4850
while (left <= right) {
4951
int mid = left+((right-left)>>1);
@@ -73,35 +75,3 @@ class Solution {
7375
}
7476
}
7577
```
76-
77-
Go Code:
78-
79-
```go
80-
func search(nums []int, target int) bool {
81-
l, r := 0, len(nums) - 1
82-
for l <= r {
83-
m := l + (r - l) / 2
84-
if nums[m] == target {
85-
return true
86-
}
87-
// 先判断哪边是递增的，再查找范围
88-
if nums[m] == nums[l] {
89-
l++
90-
} else if nums[l] < nums[m] {
91-
// 判断target是否在有序的那边就行了。
92-
if nums[l] <= target && target < nums[m] {
93-
r = m - 1
94-
} else {
95-
l = m + 1
96-
}
97-
} else if nums[l] > nums[m] {
98-
if nums[m] < target && target <= nums[r] {
99-
l = m + 1
100-
} else {
101-
r = m - 1
102-
}
103-
}
104-
}
105-
return false
106-
}
107-
```

‎animation-simulation/二分查找及其变种/leetcode153搜索旋转数组的最小值.md

Lines changed: 0 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -104,23 +104,3 @@ public:
104104
}
105105
};
106106
```
107-
108-
Go Code:
109-
110-
```go
111-
func findMin(nums []int) int {
112-
l, r := 0, len(nums) - 1
113-
for l < r {
114-
if nums[l] < nums[r] {
115-
return nums[l]
116-
}
117-
m := l + (r - l) / 2
118-
if nums[l] > nums[m] {
119-
r = m
120-
} else {
121-
l = m + 1
122-
}
123-
}
124-
return nums[l]
125-
}
126-
```

‎animation-simulation/二分查找及其变种/leetcode33不完全有序查找目标元素(不包含重复值).md

Lines changed: 2 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,8 @@
8989

9090
#### 题目代码
9191

92+
Java Code:
93+
9294
```java
9395
class Solution {
9496
public int search(int[] nums, int target) {
@@ -126,35 +128,3 @@ class Solution {
126128
}
127129
}
128130
```
129-
130-
Go Code:
131-
132-
```go
133-
func search(nums []int, target int) int {
134-
l, r := 0, len(nums) - 1
135-
for l <= r {
136-
m := (l + r) / 2
137-
if target == nums[m] {
138-
return m
139-
}
140-
// 先判断哪边是有序的
141-
if nums[m] < nums[r] {
142-
// 再判断target在左右哪边
143-
if target > nums[m] && target <= nums[r] {
144-
l = m + 1
145-
} else {
146-
r = m - 1
147-
}
148-
} else {
149-
if target < nums[m] && target >= nums[l] {
150-
r = m - 1
151-
} else {
152-
l = m + 1
153-
}
154-
}
155-
}
156-
return -1
157-
}
158-
```
159-
160-
##

‎animation-simulation/二分查找及其变种/leetcode34查找第一个位置和最后一个位置.md

Lines changed: 2 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,8 @@ int upperBound(int[] nums, int target) {
122122

123123
#### **题目完整代码**
124124

125+
Java Code:
126+
125127
```java
126128
class Solution {
127129
public int[] searchRange (int[] nums, int target) {
@@ -166,45 +168,3 @@ class Solution {
166168
}
167169
}
168170
```
169-
170-
Go Code:
171-
172-
```go
173-
func searchRange(nums []int, target int) []int {
174-
upper := upperBound(nums, target)
175-
lower := lowerBound(nums, target)
176-
177-
if (upper < lower) {
178-
return []int{-1, -1}
179-
}
180-
return []int{lower, upper}
181-
}
182-
183-
// upperBound 计算上边界
184-
func upperBound(nums []int, target int) int {
185-
l, r := 0, len(nums) - 1
186-
for l <= r {
187-
m := l + (r - l) / 2
188-
if target >= nums[m] {
189-
l = m + 1
190-
} else if target < nums[m] {
191-
r = m - 1
192-
}
193-
}
194-
return r
195-
}
196-
197-
// lowerBound 计算下边界
198-
func lowerBound(nums []int, target int) int {
199-
l, r := 0, len(nums) - 1
200-
for l <= r {
201-
m := l + (r - l) / 2
202-
if target <= nums[m] {
203-
r = m - 1
204-
} else if target > nums[m] {
205-
l = m + 1
206-
}
207-
}
208-
return l
209-
}
210-
```

‎animation-simulation/二分查找及其变种/leetcode35搜索插入位置.md

Lines changed: 2 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,8 @@
4040

4141
#### 题目代码
4242

43+
Java Code:
44+
4345
```java
4446
class Solution {
4547
public int searchInsert(int[] nums, int target) {
@@ -67,21 +69,3 @@ class Solution {
6769
```
6870

6971
Go Code:
70-
71-
```go
72-
func searchInsert(nums []int, target int) int {
73-
l, r := 0, len(nums) - 1
74-
for l <= r {
75-
m := l + (r - l) / 2
76-
if target == nums[m] {
77-
return m
78-
}
79-
if target < nums[m] {
80-
r = m - 1
81-
} else if target > nums[m] {
82-
l = m + 1
83-
}
84-
}
85-
return l
86-
}
87-
```

‎animation-simulation/二分查找及其变种/二分查找详解.md

Lines changed: 80 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -94,25 +94,50 @@ target < nums[mid] 则在左半区间继续进行搜索，即 right = mid -1；
9494

9595
下面我们来看一下二分查找的代码，可以认真思考一下 if 语句的条件，每个都没有简写。
9696

97+
Java Code:
98+
9799
```java
98-
public static int binarySearch(int[] nums,int target,int left, int right) {
99-
//这里需要注意，循环条件
100-
while (left <= right) {
101-
//这里需要注意，计算mid
102-
int mid = left + ((right - left) >> 1);
103-
if (nums[mid] == target) {
104-
return mid;
105-
}else if (nums[mid] < target) {
106-
//这里需要注意，移动左指针
107-
left = mid + 1;
108-
}else if (nums[mid] > target) {
109-
//这里需要注意，移动右指针
110-
right = mid - 1;
111-
}
100+
public static int binarySearch(int[] nums,int target,int left, int right) {
101+
//这里需要注意，循环条件
102+
while (left <= right) {
103+
//这里需要注意，计算mid
104+
int mid = left + ((right - left) >> 1);
105+
if (nums[mid] == target) {
106+
return mid;
107+
}else if (nums[mid] < target) {
108+
//这里需要注意，移动左指针
109+
left = mid + 1;
110+
}else if (nums[mid] > target) {
111+
//这里需要注意，移动右指针
112+
right = mid - 1;
112113
}
113-
//没有找到该元素，返回 -1
114-
return -1;
115114
}
115+
//没有找到该元素，返回 -1
116+
return -1;
117+
}
118+
```
119+
120+
Go Code:
121+
122+
```go
123+
func binarySearch(nums []int, target, left, right int) int {
124+
//这里需要注意，循环条件
125+
for left <= right {
126+
//这里需要注意，计算mid
127+
mid := left + ((right - left) >> 1)
128+
if nums[mid] == target {
129+
return mid
130+
} else if nums[mid] < target {
131+
//这里需要注意，移动左指针
132+
left = mid + 1
133+
} else if nums[mid] > target {
134+
//这里需要注意，移动右指针
135+
right = mid - 1
136+
}
137+
}
138+
//没有找到该元素，返回 -1
139+
return -1
140+
}
116141
```
117142

118143
二分查找的思路及代码已经理解了，那么我们来看一下实现时容易出错的地方
@@ -127,23 +152,48 @@ target < nums[mid] 则在左半区间继续进行搜索，即 right = mid -1；
127152

128153
下面我们来看一下二分查找的递归写法
129154

155+
Java Code:
156+
130157
```java
131158
public static int binarySearch(int[] nums,int target,int left, int right) {
132159

133-
if (left <= right) {
134-
int mid = left + ((right - left) >> 1);
135-
if (nums[mid] == target) {
136-
//查找成功
137-
return mid;
138-
}else if (nums[mid] > target) {
139-
//新的区间,左半区间
140-
return binarySearch(nums,target,left,mid-1);
141-
}else if (nums[mid] < target) {
142-
//新的区间，右半区间
143-
return binarySearch(nums,target,mid+1,right);
144-
}
160+
if (left <= right) {
161+
int mid = left + ((right - left) >> 1);
162+
if (nums[mid] == target) {
163+
//查找成功
164+
return mid;
165+
}else if (nums[mid] > target) {
166+
//新的区间,左半区间
167+
return binarySearch(nums,target,left,mid-1);
168+
}else if (nums[mid] < target) {
169+
//新的区间，右半区间
170+
return binarySearch(nums,target,mid+1,right);
145171
}
146-
//不存在返回-1
147-
return -1;
148172
}
173+
//不存在返回-1
174+
return -1;
175+
}
176+
```
177+
178+
Go Code:
179+
180+
```go
181+
func binarySearch(nums []int, target, left, right int) int {
182+
183+
if left <= right {
184+
mid := left + ((right - left) >> 1)
185+
if nums[mid] == target {
186+
//查找成功
187+
return mid
188+
} else if nums[mid] > target {
189+
//新的区间,左半区间
190+
return binarySearch(nums, target, left, mid-1)
191+
} else if nums[mid] < target {
192+
//新的区间，右半区间
193+
return binarySearch(nums, target, mid+1, right)
194+
}
195+
}
196+
//不存在返回-1
197+
return -1
198+
}
149199
```

‎animation-simulation/二分查找及其变种/二维数组的二分查找.md

Lines changed: 2 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,8 @@
5252

5353
#### 题目代码
5454

55+
Java Code:
56+
5557
```java
5658
class Solution {
5759
public boolean searchMatrix(int[][] matrix, int target) {
@@ -83,30 +85,3 @@ class Solution {
8385
}
8486
}
8587
```
86-
87-
Go Code:
88-
89-
```go
90-
func searchMatrix(matrix [][]int, target int) bool {
91-
if len(matrix) == 0 {
92-
return false
93-
}
94-
row, col := len(matrix), len(matrix[0])
95-
// 将二维数组拉平为一维。
96-
l, r := 0, row * col - 1
97-
for l <= r {
98-
m := l + (r - l) / 2
99-
// 将一维的坐标转换为二维
100-
x, y := m / col, m % col
101-
if matrix[x][y] == target {
102-
return true
103-
} else if matrix[x][y] < target {
104-
l = m + 1
105-
} else if matrix[x][y] > target {
106-
// 二分查找时，把所有的情况都要写出来，避免直接else
107-
r = m - 1
108-
}
109-
}
110-
return false
111-
}
112-
```

0 commit comments

Comments
 (0)