Learn practical skills, build real-world projects, and advance your career

Updated 2 years ago

# algorithms-week4-divide-and-conquer

Use the "Run" button to execute the code.

`!pip install jovian --upgrade --quiet`

`import jovian`

```
# Execute this to save new versions of the notebook
jovian.commit(project="algorithms-week4-divide-and-conquer")
```

```
[jovian] Attempting to save notebook..
```

## 1.Problem Description

`Task.`

The goal in this code problem is to implement the binary search algorithm.

`Input Format`

. The first line of the input contains an integer 𝑛 and a sequence 𝑎0 < 𝑎1 < . . . < 𝑎𝑛−1

of 𝑛 pairwise distinct positive integers in increasing order. The next line contains an integer 𝑘 and 𝑘

positive integers 𝑏0, 𝑏1, . . . , 𝑏𝑘−1.

`Constraints`

. 1 ≤ 𝑘 ≤ 105; 1 ≤ 𝑛 ≤ 3 · 104; 1 ≤ 𝑎𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛; 1 ≤ 𝑏𝑗 ≤ 109 for all 0 ≤ 𝑗 < 𝑘;

`Output Format`

. For all 𝑖 from 0 to 𝑘 − 1, output an index 0 ≤ 𝑗 ≤ 𝑛 − 1 such that 𝑎𝑗 = 𝑏𝑖 or −1 if there

is no such index.