Question

Binary search for K=12 in the array A={2, 3, 5, 7,11,15, 16,18,19}

Answer 1

def binarySearch (arr, l, r, x):
   if r >= l:
       mid = l + (r - l) // 2
       # If element is present at the middle itself
       if arr[mid] == x:
           return mid
       # If element is smaller than mid, then it can only be present in left subarray
       elif arr[mid] > x:
           return binarySearch(arr, l, mid-1, x)
       # Else the element can only be present in right subarray
       else:
           return binarySearch(arr, mid + 1, r, x)
   else:
       # Element is not present in the array
       return -1

A = [ 2, 3, 5, 7,11,15, 16,18,19 ]
K = 12

# Function call
result = binarySearch(A, 0, len(A)-1, K)

if result != -1:
   print ("Element is present at index {}".format(result))
else:
   print ("Element is not present in array")

explanation: Worstcase = O(log n)

beg = 0 and end = 8

mid = 4 so A[4] = 11 is less than K = 12

so the loop moves from 4 to 8

beg =4+1 =5 and end=8

mid = 6 and A[6] = 16 is greater than K=12

so beg = 5 and end changes to 6-1 = 5 and mid = 5

and A[5] =15 is not equal to 12 so element is not there in the array