Question

Given an array of positive integers except one negative integer. Develop a divide-conquer algorithm to find the index of the negative integer, and compute its average complexity.

Answer 1

#include <iostream>

#include <climits>

using namespace std;

void findNegativeDivideAndConquer(int arr[], int start, int end, int& ans)

{

if (start == end)

{

if (arr[start] < 0)

ans = arr[start];

return;

}

int mid = (start + end) / 2;

findNegativeDivideAndConquer(arr, start, mid, ans);

findNegativeDivideAndConquer(arr, mid + 1, end, ans);

}

int main()

{

int arr[] = { 3,4,5,2,5,-9,5,4,1,3,4,5,78};

int ans = 0;

findNegativeDivideAndConquer(arr, 0, 12, ans);

cout << "Negative Element is: " << ans<<endl;

return 0;

}

=====================================

SEE OUTPUT, Time Complexity is O(n), Average case is also N

Thanks, PLEASE COMMENT if there is any concern.

ALGORITHM f

ALGORITHM findNegativeDivideAndConquer ( arr[], start, end, ans )

START

if start == end

if (arr[start] < 0)

ans = arr[start];

return ans

mid = (start + end) / 2

findNegativeDivideAndConquer(arr, start, mid, ans)

findNegativeDivideAndConquer(arr, mid + 1, end, ans)

END

This will take O(N) time in average, PLEASE UPVOTE