Binary Search Problem
Function below handles a simple search for a needle in a haystack using the binary search algorithm.
The function is called recursively to check if a value is inside the array
See python code below.
Input:
The first line of the input contains an integer n and a sequence a 0 < a 1 < . . . < 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 , . . . , b k−1 .
Constraints:
1 ≤ n, k ≤ 10 5 ; 1 ≤ a i ≤ 10 9 for all 0 ≤ i < n; 1 ≤ b j ≤ 10 9 for all 0 ≤ j < k;
output: For all i from 0 to k − 1, output an index 0 ≤ j ≤ n − 1 such that a j = b i or −1 if there is no such index.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Uses python3 import sys # simple search for a needle in a haystack using the binary search algorithm # function called recursively to check if a value is inside the array # @return integer index of the position of the arrary element def binary_search(haystack, needle): low_point = 0 high_point = len(haystack) - 1 while True: if high_point < low_point: return -1 mid_point = (low_point + high_point) //2 if haystack[mid_point] < needle: low_point = mid_point + 1 elif haystack[mid_point] > needle: high_point = mid_point - 1 else: return mid_point if __name__ == '__main__': input = sys.stdin.read() data = list(map(int, input.split())) # define globals n_elements = data[0] haystack = data[1 : n_elements + 1] # cycle through the list of values to search for in the haystack for needle in data[n_elements + 2:]: print(binary_search(haystack, needle), end = ' ') |
Leave a Reply