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.

Please provide a solution in Java

Answer 1

Code -

public class Main
{
//function findNegativeIndex to get the index from array
static int findNegativeIndex(int a[], int s,int e){
//declare the varaible
int start = s,end = e-1,index=-1;
//while start < end
while(start<end){
//if negative number is found then return the index
if(a[start]<0)
{
index = start;
break;
}
//if negative number is found then return the index
else if(a[end]<0){
index = end;
break;
}
//else increment start and decement end
else{
start++;
end--;
}
}
return index;
}
//function to divide the array into 2 array
static int findNumberWithNegativeIndex(int a[],int size){
//varaible index be -1
int index = -1;
//divide the array from 0 to size/2 and call function findNegativeIndex
if(findNegativeIndex(a,0,size/2)!=-1){
index = findNegativeIndex(a,0,size/2);
}
//divide the array from size/2 to size and call function findNegativeIndex
else if(findNegativeIndex(a,(size/2),size)!=-1){
index = findNegativeIndex(a,(size/2),size-1);
}
//return the index value
return index;
}
   public static void main(String[] args) {
   //initiazlize an array
   int a[] = {23,56,12,-76,12,54,43,14,67,98};
   //call function to divide the array in two halfs and find the negative
   int index = findNumberWithNegativeIndex(a,a.length);
   //print the negative index value
   if(index!=-1)
   System.out.println("Negative index "+index);
   else
   System.out.println("Negative number not present ");
   }
}

Screenshots -

   int a[] = {23,56,12,-76,12,54,43,14,67,98};

Output -

Timecomplexity average - O(logn)