Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion README_EN.md
Original file line number Diff line number Diff line change
Expand Up @@ -43,7 +43,7 @@ Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF

### Searching

- [Binary Search(Algorithm Template)](./basic/searching/BinarySearch/README.md)
- [Binary Search(Algorithm Template)](./basic/searching/BinarySearch/README_EN.md)

## High Frequency Interview Questions

Expand Down
40 changes: 0 additions & 40 deletions basic/searching/BinarySearch/Main.java

This file was deleted.

24 changes: 0 additions & 24 deletions basic/searching/BinarySearch/Main.py

This file was deleted.

126 changes: 2 additions & 124 deletions basic/searching/BinarySearch/README.md
Original file line number Diff line number Diff line change
Expand Up @@ -29,128 +29,6 @@ int binarySearch2(int left, int right) {
}
```

## 题目描述
## 例题

给定一个按照升序排列的长度为 `n` 的整数数组,以及 `q` 个查询。

对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。

如果数组中不存在该元素,则返回 `-1 -1`。

**输入格式**

第一行包含整数 n 和 q,表示数组长度和询问个数。

第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。

接下来 q 行,每行包含一个整数 k,表示一个询问元素。

**输出格式**

共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回 `-1 -1`。

**数据范围**

- 1≤n≤100000
- 1≤q≤10000
- 1≤k≤10000

**输入样例:**

```
6 3
1 2 2 3 3 4
3
4
5
```

**输出样例:**

```
3 4
5 5
-1 -1
```

## 代码实现

<!-- tabs:start -->

### **Python3**

```python
n, q = map(int, input().split())
nums = list(map(int, input().split()))

for _ in range(q):
x = int(input())
left, right = 0, n - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] >= x:
right = mid
else:
left = mid + 1
if nums[left] != x:
print('-1 -1')
else:
t = left
left, right = 0, n - 1
while left < right:
mid = (left + right + 1) >> 1
if nums[mid] <= x:
left = mid
else:
right = mid - 1
print(f'{t} {left}')
```

### **Java**

```java
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), q = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
nums[i] = sc.nextInt();
}
while (q-- > 0) {
int x = sc.nextInt();
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
if (nums[left] != x) {
System.out.println("-1 -1");
} else {
int t = left;
left = 0;
right = n - 1;
while (left < right) {
int mid = (left + right + 1) >> 1;
if (nums[mid] <= x) {
left = mid;
} else {
right = mid - 1;
}
}
System.out.printf("%d %d\n", t, left);
}
}
}
}
```

<!-- tabs:end -->
- [在排序数组中查找元素的第一个和最后一个位置](/solution/0000-0099/0034.Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array/README.md)
32 changes: 32 additions & 0 deletions basic/searching/BinarySearch/README_EN.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,32 @@
# Binary Search

**Algorithm Templates:**

```java
/** check x if valid */
boolean check(int x) {}

/** template1 */
int binarySearch1(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) right = mid;
else left = mid + 1;
}
return left;
}

/** template2 */
int binarySearch2(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}
```

## Examples

- [Find First and Last Position of Element in Sorted Array](/solution/0000-0099/0034.Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array/README_EN.md)
Loading