def binarySearch(arr, low, high, item):
    if high < low:
        return -1
    
    mid = int(low + (high - low) / 2)    # Overflow Safe version of (low + high) / 2
    
    if item == arr[mid]:
        return mid
    
    if item > arr[mid]:
        return binarySearch(arr, (mid + 1), high, item)
    
    return binarySearch(arr, low, (mid - 1), item)

def binSearch(arr, low, high, item):
    if high < low:
        return -1
    
    mid = int(low + (high - low) / 2)
    
    if item == arr[mid]:
        return mid
    
    # if first half is sorted
    if arr[low] <= arr[mid]:
        # check if the element might lie within
        if item >= arr[low] and item <= arr[mid]:
            return binSearch(arr, low, mid - 1, item)
        
        return binSearch(arr, mid + 1, high, item)
    
    # else second half must be sorted, check if item might lie within
    if item >= arr[mid] and item <= arr[high]:
        return binSearch(arr, mid + 1, high, item)
    
    return binSearch(arr, low, mid - 1, item)