from time import clock import sys def main(): start = clock() fin=open("in15_8.txt","r") fout=open("out_27_15_8.txt","w") count=0 cmp=0 l=[] m=0 key=[] result=[] for line in fin: if count==0: for x in line.split(', '): l.append (int(x)) else: for x in line.split(', '): key.append (int(x)) count=count+1 t=len(l) for n in range(0,len(key)): try: k=0 j=1 while(key[n]>l[j]): cmp=cmp+1 if(key[n]==l[j]): result.append(str(j+1)) break j=j+j if(j>t-1): j=t-1 break if j<=2: lb=0 else: lb=int(j/2) if j>t-1: j=t-1 ub=j cmp=0 while lb <= ub: cmp=cmp+1 mid = int((lb + ub) / 2) if l[mid] < key[n]: cmp=cmp+1 lb = mid + 1 if key[n] < l[mid]: cmp=cmp+1 ub = mid - 1 if key[n]==l[mid]: result.append(str(mid+1)) k=k+1 break if(k==0): cmp=cmp+1 fout.write(str(-1)) result.append(str(-1)) #print "num not found" except IndexError: print "Array Index Out of Bounds Exception" result.append("Array Index Out of Bounds Exception") fout.write(",".join(result)) end = clock() time= end - start fout.write("\n Total execuion time ="+ str(time)+ " seconds") fout.write("\n Number of comparisons = "+ str(cmp)) m=sys.getsizeof(l)+sys.getsizeof(key)+sys.getsizeof(lb)+sys.getsizeof(ub)+sys.getsizeof(mid)+sys.getsizeof(fin)+sys.getsizeof(fout) fout.write("\n Memory used= "+str(m)+" bytes") fin.close() fout.close() main()