Question

Assume that we have a sorted array a[n]with n non-negative numbers.

a. Develop an algorithm using divide-and-conquer to search for an element x in this sorted array a[n]. This algorithm will take an input of a sorted array a[n], and return the index of element x is an element of a[n], or return -1if xis NOT an element of this array.

b. Analyze the time complexity of this algorithm.

Answer 1

Im divide and conquer method we divide the problem into subproblem and then solve it.

To find the index of an element in sorted array one of the divide and conquer algorthm is Binary Search algorithm

BINARY SEARCH:

In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of the middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for the right side of the middle element.

Algorithm:-

1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.
5. Else retrurn -1 ,element not present in the array

Code:-

def binarySearch (arr, l, r, x):

    if r >= l:

mid = l + (r - l) // 2

        if arr[mid] == x:

            return mid

        elif arr[mid] > x:

            return binarySearch(arr, l, mid-1, x)

        else:

            return binarySearch(arr, mid + 1, r, x)

    else:

        return -1