Question

The input is an array of N integers ( sorted ) and an integer X. The algorithm returns true if X is in the array and false if X is not in the array. Describe an algorithm that solves the problem with a worst case of O(log N) time.

Answer 1

We will use the binary search approach here, which can solve this problem in O(log N) time.

#Algorithm

L=0 #left
R=Array.length-1 #right
while L<=R:
   mid = (L+R)/2
   if (a[mid] == target):
       return true
   if (a[mid] < target):
       L = mid+1
   else:
       R = mid-1
return false

This is a divide and conquer methodology where you first take the middle element of the array and check if it is the target value, if the middle value is less than target value then you have to search on right sub array to the middle else you have to search on left subarray.

Example:

Idea TARGET 10 2 3 6 35,6810 12 ) /

here we first search middle element which is 6, as the target is 10 which is greater than 6 so we check on right subarray.

Now we find the middle element in that sub-array which is 10, and we found out the target value.

As we are dividing the array into half at every single step.

array length divides like this.

Array sizes: N -> N/2 -> N/4 -> N/8 ....

which algorithmically gives a complexity of O(logN)