Find Elements of Array w/ Quotient = y: O(m log m)

[evinda]

Hello! (Wave)

I want to describe an algorithm that given an unsorted array $B$ that stores $m$ integers, and any integer number $y$, determines if there are two elements of the array of which the quotient is equal to $y$. The time complexity of the algorithm should be $O(m \log m)$.

We have to use efficient techniques for sorting and finding an element in a sorted array.

For the sorting could we use the following algorithm? (Thinking)

procedure Heapify(A[i..j]) {
/* At the beginning,  Α[i..j-1] is partially sorted, and after the execution of  Heapify() A[i..j] is partially sorted*/
m = j;
while ((leftchild(m) ≥ i AND A[leftchild(m)] < A[m]) OR (rightchild(m) ≥ i AND A[rightchild(m)] < A[m]) {
     if (rightchild(m) ≥ i ) {
        if (A[leftchild(m)] < A[rightchild(m)])
           p = leftchild(m)
       else p = rightchild(m);
     }
     else p = i;
     swap(Α[m], A[p]);
     m = p;
}
}

How could we check if there are two elements of the array of which the quotient is equal to $y$? (Thinking)

 

[Evgeny.Makarov]

I want to describe an algorithm that given an unsorted array $B$ that stores $m$ integers, and any integer number $y$, determines if there are two elements of the array of which the quotient is equal to $y$.

What do you mean by saying that the quotient of two elements of the array is equal to $y$?

 

[evinda]

What do you mean by saying that the quotient of two elements of the array is equal to $y$?

For example, if we are given that $y=11$ and we have this array:

View attachment 3732

then since $\frac{B[0]}{B[2]}=\frac{-55}{-5}=11$ we conclude that there are two elements of the array of which the quotient is equal to $y$.

 

[Evgeny.Makarov]

You can do the following.

1. Sort the array.

2. For each element $x$, find $x/y$ in the sorted array using binary search.

 

[evinda]

2. For each element $x$, find $x/y$ in the sorted array using binary search.

So, do we have to split the array into two subarrays so that the first subarray contains all the negative numbers and the second subarray all the positive ones?
Then do we have to find the mid of each subarray and determine if we have to look at the interval $[mid+1, \text{ dimension of first subarray}-1]$ or at the interval $[0,mid-1]$ ? (Thinking)
If so, how could we find the interval that interests us?

 

[Evgeny.Makarov]

So, do we have to split the array into two subarrays so that the first subarray contains all the negative numbers and the second subarray all the positive ones?

I don't see how this helps. My description of the algorithm does not mention positive and negative numbers.

Then do we have to find the mid of each subarray and determine if we have to look at the interval $[mid+1, \text{ dimension of first subarray}-1]$ or at the interval $[0,mid-1]$ ?

Do you know why computing Fibonacci numbers by definition is slow? Because you have to compute the same Fibonacci number many times. For example, to compute $\varphi_5$ you have to find $\varphi_4$ and $\varphi_3$. But to compute $\varphi_4$, you have to find $\varphi_2$ and $\varphi_3$ again. Thus, you compute $\varphi_3$ twice one can check that $\varphi_2$ is computed three times. In general, computing $\varphi_n$ takes time exponential in $n$.

I am saying this because your way of asking questions reminds computing Fibonacci numbers. If I remember right, there have been several pretty long threads on this forum devoted to the analysis and complexity of binary search. In fact, you answered questions in some of them. If you are going to ask questions about it in every new thread that touches on binary search and these questions will produce similar discussions, the total size of these discussions will be exponential. I don't think this is productive.

However, if you insist, please start a new thread about binary search. Use Google to search for "binary search site:mathhelpboards.com" (or use search on this forum) to find all threads related to binary search in the last six months. In the new thread, list all found threads and explain why your new question is not in one of them.

 

[evinda]

I don't see how this helps. My description of the algorithm does not mention positive and negative numbers.

Do you know why computing Fibonacci numbers by definition is slow? Because you have to compute the same Fibonacci number many times. For example, to compute $\varphi_5$ you have to find $\varphi_4$ and $\varphi_3$. But to compute $\varphi_4$, you have to find $\varphi_2$ and $\varphi_3$ again. Thus, you compute $\varphi_3$ twice one can check that $\varphi_2$ is computed three times. In general, computing $\varphi_n$ takes time exponential in $n$.

I am saying this because your way of asking questions reminds computing Fibonacci numbers. If I remember right, there have been several pretty long threads on this forum devoted to the analysis and complexity of binary search. In fact, you answered questions in some of them. If you are going to ask questions about it in every new thread that touches on binary search and these questions will produce similar discussions, the total size of these discussions will be exponential. I don't think this is productive.

However, if you insist, please start a new thread about binary search. Use Google to search for "binary search site:mathhelpboards.com" (or use search on this forum) to find all threads related to binary search in the last six months. In the new thread, list all found threads and explain why your new question is not in one of them.

I think that I have understood Binary search.
I haven't understood how we could apply it in this case.
The algorithm finds the position of a specific input value within an array sorted by key value.
So we find the mid and if $A[\text{ mid }]<\text{key}$ we look at the interval $[\text{ mid+1, high}]$ where high is the dimension of the subarray we are looking at minus 1, otherwise we are looking at the interval $[\text{low,mid-1}]$ where low is the position that corresponds to the first element of the subarray we are looking at.
But in our case we have to consider two elements in order to check if their fraction is equal to $y$.
How can we apply then the Binary search? (Thinking)

 

[Evgeny.Makarov]

Let's look carefully at what you and I are saying.

The algorithm finds the position of a specific input value within an array sorted by key value.

I am not sure what "sorted by key value" means.

So we find the mid and if $A[\text{ mid }]<\text{key}$

Judging by this line, [m]key[/m] is what the algorithm searches in the array. I don't understand then why you make a distinction in the previous quote between "a specific input value" and "key value".

Binary search has two inputs: an array and a value to search. (The auxiliary recursive procedure has two more arguments: the lower and upper indices between which to search.)

But in our case we have to consider two elements in order to check if their fraction is equal to $y$.
How can we apply then the Binary search?

Let me say it again.

1. Sort the array.

2. For each element $x$, find $x/y$ in the sorted array using binary search.

I described both inputs to binary search.

 

[evinda]

We want to determine if there are two elements such that their quotient is equal to $y$.
So, do we have to find the value $\frac{\text{mid}}{y}$ and check if it is greater / less or equal to $\text{mid}+1$?
Or have I understood it wrong? (Worried)

 

[Evgeny.Makarov]

We want to determine if there are two elements such that their quotient is equal to $y$.
So, do we have to find the value $\frac{\text{mid}}{y}$ and check if it is greater / less or equal to $\text{mid}+1$?

I don't know what [m]mid[/m] is.

I don't want to look inside binary search in this thread. It is enough to treat binary search as a black box that takes two inputs: an array and a value and returns yes or no depending on whether the value is in the array. Also, it does it in time $O(\log n)$ where $n$ is the number of elements in the array.

 

[evinda]

I don't know what [m]mid[/m] is.

I don't want to look inside binary search in this thread. It is enough to treat binary search as a black box that takes two inputs: an array and a value and returns yes or no depending on whether the value is in the array. Also, it does it in time $O(\log n)$ where $n$ is the number of elements in the array.

So do we have to call for each value $x$ of the array the Binary search with parameter $\frac{x}{y}$ and number of elements $m$, in order to check if there are two elements of which the quotient is equal to $y$? (Thinking)

 

[Evgeny.Makarov]

So do we have to call for each value $x$ of the array the Binary search with parameter $\frac{x}{y}$ and number of elements $m$, in order to check if there are two elements of which the quotient is equal to $y$?

Yes. I hope it is clear, why.

 

[evinda]

Yes. I hope it is clear, why.

So, does the algorithm have to look like that? (Thinking)

Algorithm(B[0...m-1],y){
  low=0;
  high=m-1;
  found=0;
  Heapsort(B[0...m-1],m);
  while (found==0 and i<m){
          l=B[i]/y;
          k=BinarySearch(B,l,low,high);
          if (k==l) found=1;
          i++;
  }
}

If so, do we have to change the Binary Search so that it returns [m]A[position][/m] instead of [m] position [/m], so that we we can check if the $\frac{x}{y}$ was found? (Thinking)
With [m] position [/m] I mean the last position that the algorithm Binary Search checks.

 

[Evgeny.Makarov]

So, does the algorithm have to look like that?

The counter [m]i[/m] is not defined. More importantly, I don't understand why you compare the value returned by BinarySearch with B / y.

If so, do we have to change the Biary Search so that it returns [m]A[position][/m] instead of [m] position [/m], so that we we can check if the $\frac{x}{y}$ was found?

It depends on how BinarySearch signals that it found the element. You are only interested in whether it has found B / y or not.

 

[evinda]

The counter [m]i[/m] is not defined. More importantly, I don't understand why you compare the value returned by BinarySearch with B / y.

Oh, I forgot to initialize [m] i [/m]... I am sorry... (Blush)
So, should it be like that? (Thinking)

Algorithm(B[1...m],y){
  low=1;
  high=m;
  found=0;
  i=1;
  Heapsort(B[1...m],m);
  while (found==0 and i<=m){
          l=B[i]/y;
          k=BinarySearch(B,l,low,high);
          if (k!=0) found=1;
          i++;
  }
}

int BinarySearch(int A[], int key, int low, int high){
   int mid;
   if (high < low) return 0;
   else{
       mid=low+floor((high-low)/2);
       if (A[mid] > key)
           return BinarySearch(A, key,low, mid-1);
       else if (A[mid] < key)
           return BinarySearch(A, key, mid+1, high);
       else
          return mid;
    }
}

It depends on how BinarySearch signals that it found the element. You are only interested in whether it has found B / y or not.

If the position that it returns isn't equal to [m] 0 [/m] then we know that the [m] key [/m] we were looking at was found, right? (Thinking)

 

[evinda]

Also we have to check seperately the case [m] y=0 [/m], right?
In this case do we have to call the [m]BinarySearch[/m] with [m] key=0[/m] in order to check if an element of the array has the value [m] 0 [/m] and then traverse the array to check if there is a nonzero element? (Thinking)

 

[Evgeny.Makarov]

The code looks OK.

If the position that it returns isn't equal to [m] 0 [/m] then we know that the [m] key [/m] we were looking at was found, right?

Yes.

Also we have to check seperately the case [m] y=0 [/m], right?

You can check for zero elements of the array in the loop after sorting. If B == 0 and y == 0, there is no reason in calling BinarySearch with B / y.

 

[evinda]

The code looks OK.

Yes.

Nice! (Happy)

You can check for zero elements of the array in the loop after sorting. If B == 0 and y == 0, there is no reason in calling BinarySearch with B / y.

Could we do it like that? (Thinking)

Algorithm(B[1...m],y){
  low=1;
  high=m;
  found=0;
  i=1;
  j=1;
  count=0;
  Heapsort(B[1...m],m);
  if (y==0){
     while (j<=m){
             if (B[j]==0) {
                count++;
             }
             j++;
     }
     if (count!=m) found=1;
     
  }
  else{
      while (found==0 and i<=m){
              if (B[i]!=0){
                 l=B[i]/y;
                 k=BinarySearch(B,l,low,high);
                 if (k!=0) found=1;
                 i++;
              }
      
      }
  }
}

 

[Evgeny.Makarov]

What is the reason for counting the number of zero elements in B and declaring success if not all elements of B are zeros? What if no element of B is a zero?

 

[evinda]

What is the reason for counting the number of zero elements in B and declaring success if not all elements of B are zeros? What if no element of B is a zero?

I thought that we could do it like that, because if there are only zeros in the array we cannot find two element such that their quotient is equal to $0$ since $\frac{0}{0}$ is not defined. And if there is at least one nonzero element, there will be two elements such that their quotient is equal to $0$. So, in this case [m] found [/m] will get the value [m] 1 [/m]. If there is no element that is equal to zero, the variable [m] found [/m] will not change, that means that there aren't two elements such that their quotient is equal to $0$.

Isn't it right? (Thinking)

- - - Updated - - -

But like that we don't check the case that there is no element that is equal to $0$, right?

So should the following command be executed:

[m] if (count!=m and count!=0) found=1; [/m]

instead of this one:

[m] if (count!=m) found=1; [/m]

? (Thinking)

 

[Evgeny.Makarov]

So should the following command be executed:

[m] if (count!=m and count!=0) found=1; [/m]

instead of this one:

[m] if (count!=m) found=1; [/m]

Yes, this makes sense.