Overview In this assignment we will implement three different algorithms that so

Question

Overview In this assignment we will implement three different algorithms that solve the same problem, analyze each algorithm, and then verify the analysis by collecting and graphing run time data Suppose you have a sorted array of positive and negative integers (no zeros!) and would like to determine if there exists some value x such that both x and -x are irn the array. Here are three algorithms that solve this problem: Algorithm #1: For each element in the array, do a sequential search to see if the corresponding element is in the array. Sequential search means you start at the beginning of the array and examine each element one by one until the element you re looking for is found Algorithm #2: For each element in the array, do a binary search to see if the corresponding element is in the array. Here is pseudocode for an iterative version of the binary search algorithm: input: x (value we are searching for) first last arraysize-1 while first

Explanation / Answer

here is your answer : ------------>>>>>>

Algorithm 1 = order n square;

Algorithm 2 = Order n log n;

Algorithm 3 = Order n;

public class FindX_X{
public static boolean Algorithm1(int[] arr){
  int n = arr.length;
  int cor = 0;
  for(int i = 0;i<n;i++){
   cor = (-1)*(arr[i]);
   for(int j = i+1;j < n;j++){
    if(arr[j] == cor){
     return true;
    }
   }
  }
  return false;
}

public static boolean Algorithm2(int[] arr){
  int n = 0;
  int t = arr.length;
  int cor = 0;
  int middle = 0;
  for(int i = 0;i<t;i++){
   cor = (-1)*(arr[i]);
   n = arr.length - 1;
   for(int j = 0;j <= n;){
    middle = (j + n)/2;
    if(arr[middle] == cor){
     System.out.println("X = "+cor+"     "+arr[i]);
     return true;
    }else if(arr[middle] > cor){
     n = middle -1;
    }else{
     j = middle + 1;
    }
   }
  }

  return false;
}

public static boolean Algorithm3(int[] arr){
  int i = 0;
  int j = arr.length - 1;
  int sum = -1;
  while(i != j){
   sum = arr[i] + arr[j];
   if(sum == 0){
    return true;
   }else if(sum < 0){
    i++;
   }else{
    j--;
   }
  }

  return false;
}
}

import java.util.Random;
import java.util.Arrays;

public class FindX_XTest{
public static void main(String[] args) {
  Random rand = new Random();
  int s = 100000;
  int[] arr = new int[s];
  for(int i = 0;i<s;i++){
   arr[i] = rand.nextInt();
  }
  Arrays.sort(arr);
  long startTime = System.currentTimeMillis();
  if(FindX_X.Algorithm1(arr)){
   System.out.println("Find in algo 1");
  }
  long endTime = System.currentTimeMillis();
  System.out.println("Total Time for algo 1 = "+(endTime - startTime)+" milli seconds");
  startTime = System.currentTimeMillis();
  if(FindX_X.Algorithm2(arr)){
   System.out.println("Find in Algo 2");
  }
  endTime = System.currentTimeMillis();
  System.out.println("Total Time for algo 2 = "+(endTime - startTime)+" milli seconds");
  startTime = System.currentTimeMillis();
  if(FindX_X.Algorithm3(arr)){
   System.out.println("find in algo 3");
  }
  endTime = System.currentTimeMillis();
  System.out.println("Total Time for algo 3 = "+(endTime - startTime)+" milli seconds");
}
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.