fork(7) download
copy 
  1. import sys,math
  2.  
  3. def bsearch(arr, k):
  4.     l0 = 0
  5.     r0 = len(arr) - 1
  6.     if (len(arr) > 1):
  7.         q = int(round(math.sqrt(len(arr)),0))
  8.         B = []
  9.         i = 0
  10.         pos = []
  11.         while (i <= len(arr)-1):
  12.             B.append(arr[i])
  13.             pos.append(i)
  14.             i = i + q
  15.  
  16.         l = 0
  17.         r = len(B) - 1
  18.         m = 0
  19.         arr_to_k = -1
  20.         while (l <= r):
  21.             m = (l + r)/2
  22.             if (B[m] < k):
  23.                 if (m == len(B) - 1):
  24.                     l0 = pos[m]
  25.                     r0 = len(arr) - 1
  26.                     l = r + 1
  27.                 elif (arr_to_k == 2):
  28.                     l0 = pos[m]
  29.                     r0 = pos[m+1]
  30.                     l = r + 1
  31.                 else:
  32.                     l = m + 1
  33.                     arr_to_k = 1
  34.  
  35.             elif (B[m] == k):
  36.                 j = pos[m]
  37.                 while (arr[j] == k):
  38.                     j = j - 1
  39.                 return j + 1
  40.             else:
  41.                 if (m == 0):
  42.                     l0 = 0
  43.                     r0 = pos[m]
  44.                     l = r + 1
  45.                 elif (arr_to_k == 1):
  46.                     l0 = pos[m-1]
  47.                     r0 = pos[m]
  48.                     l = r + 1
  49.                 else:
  50.                     r = m - 1     
  51.                     arr_to_k = 2
  52.  
  53.     l = l0
  54.     r = r0
  55.     m = 0
  56.     while (l <= r):
  57.         m=(l + r)/2
  58.         if (arr[m] < k):
  59.             l = m + 1
  60.         elif (arr[m] == k):
  61.             return m
  62.         else:
  63.             r = m - 1
  64.     return -1
  65.  
  66. arr = []
  67. tokenizedInput = sys.stdin.read().split()
  68. n = int(tokenizedInput[0])
  69. m = int(tokenizedInput[1])
  70. for i in range(2,n+2):
  71.     arr.append(int(tokenizedInput[i]))
  72. for i in range(n+2, n+2+m):
  73.     k = int(tokenizedInput[i])
  74.     print bsearch(arr,k)
Success #stdin #stdout 0.01s 7732KB
comments (?)
stdin
copy 
5 4
2 4 7 7 9
7
10
4
2
stdout
copy 
2
-1
1
0
https://ideone.com/0CSrEj
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!