![[UCSD白板题] Binary Search [UCSD白板题] Binary Search](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Problem Introduction
In this problem, you will implemented the binary search algorithm that allows searching very efficiently(even huge) lists provided that the list is sorted.
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 \(n\) and a sequence \(a_0<a_1<\cdots<a_{n-1}\) of \(n\) pairwise distinct positive integers in increasing order. The next line contains an integer \(k\) and \(k\) positive integers \(b_0,b_1,\cdots,b_{k-1}\).
Constraints.\(1 \leq n,k \leq 10^5; 1 \leq a_i \leq 10^9\) for all \(0 \leq i < n; 1 \leq b_j \leq 10^9\) for all \(0 \leq j \leq k\).
Output Format.For all \(i\) from \(0\) to \(k-1\),output an index \(0 \leq j \leq n-1\) such that \(a_j=b_i\) or \(-1\) if there is no such index.
Sample 1.
Input:
5 1 5 8 12 13
5 8 1 23 1 11
Output:
2 0 -1 0 -1
Solution
# Uses python3
import sys
def binary_search(a, x):
left, right = 0, len(a)
while left < right:
mid = left + (right - left) // 2
if x == a[mid]:
return mid
elif x < a[mid]:
right = mid
else:
left = mid + 1
return -1
def linear_search(a, x):
for i in range(len(a)):
if a[i] == x:
return i
return -1
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
n = data[0]
m = data[n + 1]
a = data[1 : n + 1]
for x in data[n + 2:]:
print(binary_search(a, x), end = ' ')