Coverage for local/lib/python2.7/site-packages/sage/data_structures/binary_search.pyx : 95%

# We can probably get away with only having the mpz_binary_searches in here. 

# I'm too scared to get rid of it at 2am though. 

cdef Py_ssize_t binary_search(Py_ssize_t* v, Py_ssize_t n, Py_ssize_t x, Py_ssize_t* ins): 

""" 

Find the position of the integer x in the array v, which has length n. 

Returns -1 if x is not in the array v, and in this case ins is 

set equal to the position where x should be inserted in order to 

obtain an ordered array. 

""" 

if n == 0: 

ins[0] = 0 

return -1 

cdef Py_ssize_t i, j, k 

i = 0 

j = n-1 

while i<=j: 

if i == j: 

if v[i] == x: 

ins[0] = i 

return i 

if v[i] < x: 

ins[0] = i + 1 

else: 

ins[0] = i 

return -1 

k = (i+j)/2 

if v[k] > x: 

j = k-1 

elif v[k] < x: 

i = k+1 

else: # only possibility is that v[k] == x 

ins[0] = k 

return k 

# end while 

ins[0] = j+1 

return -1 

cdef Py_ssize_t binary_search0(Py_ssize_t* v, Py_ssize_t n, Py_ssize_t x): 

""" 

Find the position of the int x in the array v, which has length n. 

Returns -1 if x is not in the array v. 

""" 

if n == 0: 

return -1 

cdef Py_ssize_t i, j, k 

i = 0 

j = n-1 

while i<=j: 

if i == j: 

if v[i] == x: 

return i 

return -1 

k = (i+j)/2 

if v[k] > x: 

j = k-1 

elif v[k] < x: 

i = k+1 

else: # only possibility is that v[k] == x 

return k 

return -1