# It returns location of x in given array arr
# if present, else returns -1
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) / 2; #extracting the middle element from the array
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1 #l is initialised to the rightmost element of the middle so that the search could be started from there the next time
# If x is smaller, ignore right half
elif x