Skip to content

Commit 25ad730

Browse files
krahetskrahets
authored
Merge pull request krahets#177 from danielsss/master
Add the TypeScript code and docs for Chapter of Binary Search
2 parents eeb0aec + bb95d47 commit 25ad730

File tree

3 files changed

+114
-25
lines changed

3 files changed

+114
-25
lines changed

‎codes/typescript/chapter_searching/binary_search.ts

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
* File: binary_search.ts
3+
* Created Time: 2022-12-27
4+
* Author: Daniel (better.sunjian@gmail.com)
5+
*/
6+
7+
/* 二分查找（双闭区间） */
8+
const binarySearch = function (nums: number[], target: number): number {
9+
// 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
10+
let i = 0, j = nums.length - 1;
11+
// 循环，当搜索区间为空时跳出（当 i > j 时为空）
12+
while (i <= j) {
13+
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m
14+
if (nums[m] < target) { // 此情况说明 target 在区间 [m+1, j] 中
15+
i = m + 1;
16+
} else if (nums[m] > target) { // 此情况说明 target 在区间 [i, m-1] 中
17+
j = m - 1;
18+
} else { // 找到目标元素，返回其索引
19+
return m;
20+
}
21+
}
22+
return -1; // 未找到目标元素，返回 -1
23+
}
24+
25+
/* 二分查找（左闭右开） */
26+
const binarySearch1 = function (nums: number[], target: number): number {
27+
// 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
28+
let i = 0, j = nums.length;
29+
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
30+
while (i < j) {
31+
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m
32+
if (nums[m] < target) { // 此情况说明 target 在区间 [m+1, j] 中
33+
i = m + 1;
34+
} else if (nums[m] > target) { // 此情况说明 target 在区间 [i, m] 中
35+
j = m;
36+
} else { // 找到目标元素，返回其索引
37+
return m;
38+
}
39+
}
40+
return -1; // 未找到目标元素，返回 -1
41+
}
42+
43+
44+
/* Driver Code */
45+
const target = 6;
46+
const nums = [ 1, 3, 6, 8, 12, 15, 23, 67, 70, 92 ];
47+
48+
/* 二分查找（双闭区间） */
49+
let index = binarySearch(nums, target);
50+
console.info('目标元素 6 的索引 = %d', index);
51+
52+
/* 二分查找（左闭右开） */
53+
index = binarySearch1(nums, target);
54+
console.info('目标元素 6 的索引 = %d', index);

‎docs/chapter_hashing/hash_map.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -646,7 +646,7 @@ $$
646646
/* 添加操作 */
647647
public set(key: number, val: string) {
648648
let index = this.hashFunc(key);
649-
this.bucket[index] = new Entry(index, val);
649+
this.bucket[index] = new Entry(key, val);
650650
}
651651

652652
/* 删除操作 */

‎docs/chapter_searching/binary_search.md

Lines changed: 59 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -116,17 +116,17 @@ $$
116116
=== "Go"
117117

118118
```go title="binary_search.go"
119-
/* 二分查找（左闭右开） */
120-
func binarySearch1(nums []int, target int) int {
121-
// 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
122-
i, j := 0, len(nums)
123-
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
124-
for i < j {
119+
/* 二分查找（双闭区间） */
120+
func binarySearch(nums []int, target int) int {
121+
// 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
122+
i, j := 0, len(nums)-1
123+
// 循环，当搜索区间为空时跳出（当 i > j 时为空）
124+
for i <= j {
125125
m := (i + j) / 2 // 计算中点索引 m
126-
if nums[m] < target { // 此情况说明 target 在区间 [m+1, j) 中
126+
if nums[m] < target { // 此情况说明 target 在区间 [m+1, j] 中
127127
i = m + 1
128-
} else if nums[m] > target { // 此情况说明 target 在区间 [i, m) 中
129-
j = m
128+
} else if nums[m] > target { // 此情况说明 target 在区间 [i, m-1] 中
129+
j = m - 1
130130
} else { // 找到目标元素，返回其索引
131131
return m
132132
}
@@ -161,7 +161,23 @@ $$
161161
=== "TypeScript"
162162

163163
```typescript title="binary_search.ts"
164-
164+
/* 二分查找（双闭区间） */
165+
const binarySearch = function (nums: number[], target: number): number {
166+
// 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
167+
let i = 0, j = nums.length - 1;
168+
// 循环，当搜索区间为空时跳出（当 i > j 时为空）
169+
while (i <= j) {
170+
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m
171+
if (nums[m] < target) { // 此情况说明 target 在区间 [m+1, j] 中
172+
i = m + 1;
173+
} else if (nums[m] > target) { // 此情况说明 target 在区间 [i, m-1] 中
174+
j = m - 1;
175+
} else { // 找到目标元素，返回其索引
176+
return m;
177+
}
178+
}
179+
return -1; // 未找到目标元素，返回 -1
180+
}
165181
```
166182

167183
=== "C"
@@ -208,9 +224,9 @@ $$
208224
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
209225
while (i < j) {
210226
int m = (i + j) / 2; // 计算中点索引 m
211-
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
227+
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
212228
i = m + 1;
213-
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
229+
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m] 中
214230
j = m;
215231
else // 找到目标元素，返回其索引
216232
return m;
@@ -230,9 +246,9 @@ $$
230246
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
231247
while (i < j) {
232248
int m = (i + j) / 2; // 计算中点索引 m
233-
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
249+
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
234250
i = m + 1;
235-
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
251+
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m] 中
236252
j = m;
237253
else // 找到目标元素，返回其索引
238254
return m;
@@ -252,9 +268,9 @@ $$
252268
# 循环，当搜索区间为空时跳出（当 i = j 时为空）
253269
while i < j:
254270
m = (i + j) // 2 # 计算中点索引 m
255-
if nums[m] < target: # 此情况说明 target 在区间 [m+1, j) 中
271+
if nums[m] < target: # 此情况说明 target 在区间 [m+1, j] 中
256272
i = m + 1
257-
elif nums[m] > target: # 此情况说明 target 在区间 [i, m) 中
273+
elif nums[m] > target: # 此情况说明 target 在区间 [i, m] 中
258274
j = m
259275
else: # 找到目标元素，返回其索引
260276
return m
@@ -271,9 +287,9 @@ $$
271287
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
272288
for i < j {
273289
m := (i + j) / 2 // 计算中点索引 m
274-
if nums[m] < target { // 此情况说明 target 在区间 [m+1, j) 中
290+
if nums[m] < target { // 此情况说明 target 在区间 [m+1, j] 中
275291
i = m + 1
276-
} else if nums[m] > target { // 此情况说明 target 在区间 [i, m) 中
292+
} else if nums[m] > target { // 此情况说明 target 在区间 [i, m] 中
277293
j = m
278294
} else { // 找到目标元素，返回其索引
279295
return m
@@ -294,9 +310,9 @@ $$
294310
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
295311
while (i < j) {
296312
let m = parseInt((i + j) / 2); // 计算中点索引 m ，在 JS 中需使用 parseInt 函数取整
297-
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
313+
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
298314
i = m + 1;
299-
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
315+
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m] 中
300316
j = m;
301317
else // 找到目标元素，返回其索引
302318
return m;
@@ -309,7 +325,23 @@ $$
309325
=== "TypeScript"
310326

311327
```typescript title="binary_search.ts"
312-
328+
/* 二分查找（左闭右开） */
329+
const binarySearch1 = function (nums: number[], target: number): number {
330+
// 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
331+
let i = 0, j = nums.length;
332+
// 循环，当搜索区间为空时跳出（当 i = j 时为空）
333+
while (i < j) {
334+
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m
335+
if (nums[m] < target) { // 此情况说明 target 在区间 [m+1, j] 中
336+
i = m + 1;
337+
} else if (nums[m] > target) { // 此情况说明 target 在区间 [i, m] 中
338+
j = m;
339+
} else { // 找到目标元素，返回其索引
340+
return m;
341+
}
342+
}
343+
return -1; // 未找到目标元素，返回 -1
344+
}
313345
```
314346

315347
=== "C"
@@ -330,9 +362,9 @@ $$
330362
while (i < j)
331363
{
332364
int m = (i + j) / 2; // 计算中点索引 m
333-
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
365+
if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
334366
i = m + 1;
335-
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
367+
else if (nums[m] > target) // 此情况说明 target 在区间 [i, m] 中
336368
j = m;
337369
else // 找到目标元素，返回其索引
338370
return m;
@@ -407,7 +439,10 @@ $$
407439
=== "TypeScript"
408440

409441
```typescript title=""
410-
442+
// (i + j) 有可能超出 Number 的取值范围
443+
let m = Math.floor((i + j) / 2);
444+
// 更换为此写法则不会越界
445+
let m = Math.floor(i + (j - i) / 2);
411446
```
412447

413448
=== "C"

0 commit comments

Comments
 (0)