Binary Search Problem<\/p>\n
Function below handles a simple search for a needle in a haystack using the binary search algorithm.<\/p>\n
The function is called recursively to check if a value is inside the array<\/p>\n
See python code below.<\/p>\n
Input:<\/strong> Constraints:<\/strong> output: For all i from 0 to k \u2212 1, output an index 0 \u2264 j \u2264 n \u2212 1 such that\u00a0\u00a0a j = b i or \u22121 if there is no such index.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30,31],"series":[],"class_list":["post-133","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code","tag-binary-search"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/133","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=133"}],"version-history":[{"count":3,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/133\/revisions"}],"predecessor-version":[{"id":144,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/133\/revisions\/144"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=133"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nThe first line of the input contains an integer n and a sequence a 0 < a 1 < . . . < a n\u22121 of
\nn pairwise distinct positive integers in increasing order. The next line contains an integer k and k positive integers b 0 , b 1 , . . . , b k\u22121 .<\/p>\n
\n1 \u2264 n, k \u2264 10 5 ; 1 \u2264 a i \u2264 10 9 for all 0 \u2264 i < n; 1 \u2264 b j \u2264 10 9 for all 0 \u2264 j < k;<\/p>\n# Uses python3\r\nimport sys\r\n\r\n# simple search for a needle in a haystack using the binary search algorithm\r\n\r\n# function called recursively to check if a value is inside the array\r\n# @return integer index of the position of the arrary element\r\ndef binary_search(haystack, needle):\r\n low_point = 0\r\n high_point = len(haystack) - 1\r\n\r\n while True:\r\n if high_point < low_point:\r\n return -1\r\n mid_point = (low_point + high_point) \/\/2\r\n if haystack[mid_point] < needle:\r\n low_point = mid_point + 1\r\n elif haystack[mid_point] > needle:\r\n high_point = mid_point - 1\r\n else:\r\n return mid_point\r\n\r\n\r\nif __name__ == '__main__':\r\n input = sys.stdin.read()\r\n data = list(map(int, input.split()))\r\n # define globals\r\n n_elements = data[0]\r\n haystack = data[1 : n_elements + 1]\r\n\r\n # cycle through the list of values to search for in the haystack\r\n for needle in data[n_elements + 2:]:\r\n print(binary_search(haystack, needle), end = ' ')<\/pre>\n