<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Binary Search
Step2:  straight forward binary search
implementing this using a while loop
Step4:  Recursive attempt at binary search
Note
Step5:  Comparing the two
Step6:  So a straightforward algo is faster.
testing got it correct
<ASSISTANT_TASK:>
Python Code:
data = [i for i in range(10000)]
data[:10]
Explanation: Binary Search:
start with a sorted list of data
see if the mid value is what we're looking for
if item is lower than the mid, make mid-1 the new high point
if item is higher than the mid, make mid+1 the new low point
keep going until list is exhausted or item is found
The data doesn't really matter, so using a simple range of numbers:
End of explanation
def binary_search(data, item):
    takes in a sorted list of items, and item to find, and returns item number if item found, -1 if not found
    
    low = 0
    high = len(data) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == item:
            return mid
        elif data[mid] < item:
            low = mid + 1
        else:
            high = mid - 1
    return -1
binary_search(data, 10)
Explanation: straight forward binary search
implementing this using a while loop
End of explanation
def binary_search_recursive(data, item):
    
    takes in a sorted list and item to find
    returns index number if found, -1 if not
    
    def recur(low, high):
        mid = (low + high) // 2   
        if low > high:
            return -1
        elif item < data[mid]:
            return recur(low, mid-1)
        elif item > data[mid]:
            return recur(mid+1, high)
        else:
            #print('found', item, 'in position', mid)
            return mid
        
    return recur(0, len(data) - 1)
binary_search_recursive(data, 2)
Explanation: Recursive attempt at binary search
Note: this only prints out yes if item found, msg otherwise
End of explanation
# non-recursive
%timeit(binary_search(data, 2))
# recursive
%timeit(binary_search_recursive(data, 2))
Explanation: Comparing the two
End of explanation
for i in range(0,100):
    assert i == binary_search(data, i)
    assert i == binary_search_recursive(data,i)
binary_search(data,-1)
binary_search_recursive(data,-1)
Explanation: So a straightforward algo is faster.
testing got it correct:
End of explanation
<END_TASK>