Find p in a Sorted Array with Unique Property | O(log n) Algorithm

  • Thread starter Jairo Rojas
  • Start date
  • Tags
    Algorithm
In summary: I think the best way to do it is to have a local variable that keeps track of the current mid and then just compare the two values in that variable.int mid=(first+last)/2T(E,0,mid,index)T(E,mid+1,last,index)if(E[mid]<E[mid+1])index=mid
  • #1
Jairo Rojas
17
0

Homework Statement


Suppose you are given an array A of n distinct integers with the following property: There exists a unique index p such that the values of A[1 . . . p] are decreasing and the values of A[p . . . n] are is increasing. For instance, in the example below we have n = 10 and p = 4:
A = [20, 18, 12, 10, 50, 51, 69, 94, 103, 111]
Design a O(log n) algorithm to find p given an array A with the above property

Homework Equations

The Attempt at a Solution


[/B]
I just used the mergesort and compared the rightmost point of the left array with the leftmost point of the right array. The running time has to be logn I think.

Code:
T(E[]Array,int first, int last, int index)
{
if(first<last)
{
int mid=(first+last)/2
T(E,0,mid,index)
T(E,mid+1,last,index)
if(E[mid]<E[mid+1])
index=mid
return;
}
return;
}[/B]
 
Last edited:
Physics news on Phys.org
  • #2
You cannot use an unmodified sorting algorithm, those don't run in faster than linear time.

Your function calls two functions with half the range each, that leads to a linear runtime if nothing else happens.
Also, for every reasonable language, your function ignores whatever the inner function calls do, which means you do not get a reasonable output.

The idea to compare two elements in the middle recursively is good, but you cannot do that everywhere. The comparison has to determine where to continue searching.
 
  • #3
mfb said:
You cannot use an unmodified sorting algorithm, those don't run in faster than linear time.

Your function calls two functions with half the range each, that leads to a linear runtime if nothing else happens.
Also, for every reasonable language, your function ignores whatever the inner function calls do, which means you do not get a reasonable output.

The idea to compare two elements in the middle recursively is good, but you cannot do that everywhere. The comparison has to determine where to continue searching.
how would you do it?. I think that to fix your inquiry about to determine if the function continues searching you just put the comparison part on top of the algorithm.
Code:
T(E[]Array,int first, int last, int index)
{
if(first<last)
{
int mid=(first+last)/2
if(E[mid]<E[mid+1])
{
index=mid
return;
}
T(E,0,mid,index)
T(E,mid+1,last,index)

}
return;
}
[/B]
 
  • #4
Jairo Rojas said:
how would you do it?
mfb said:
You cannot use an unmodified sorting algorithm, those don't run in faster than linear time.

Your function calls two functions with half the range each, that leads to a linear runtime if nothing else happens.
Also, for every reasonable language, your function ignores whatever the inner function calls do, which means you do not get a reasonable output.

The idea to compare two elements in the middle recursively is good, but you cannot do that everywhere. The comparison has to determine where to continue searching.

I think that now this is better.
Code:
int initial_first 
int initial_last 
T(E[]Array,int first,int last,int index)
mid=(first+last)/2    
if(mid!=initial_first and mid!= initial_last )               
    if(Last-first==0) 
         if(E[mid-1]>E[mid] and E[mid+1]>E[mid]) 
         index=mid
     else
       return;
    else if(E[mid-1]>E[mid] and E[mid+1]>E[mid])
     index=mid
     return;
    else if(E[mid-1]<E[mid] and E[mid+1]>E[mid])
     T(E[]Array,0,mid,index)
    else
      T(E[]Array,mid+1,last,index)
else
return;
[\code]
 
  • #5
The idea is right, but there are some things that need fixing. Where is the point in checking "if(E[mid-1]>E[mid] and E[mid+1]>E[mid]) " twice?
If last-first=0, going down another layer of recursion does not make sense, but if you set index=mid you do not return - and otherwise you return with nothing.

initial_first and initial_last are not initialized, but if they would you might return with nothing.
 
  • #6
mfb said:
The idea is right, but there are some things that need fixing. Where is the point in checking "if(E[mid-1]>E[mid] and E[mid+1]>E[mid]) " twice?
If last-first=0, going down another layer of recursion does not make sense, but if you set index=mid you do not return - and otherwise you return with nothing.

initial_first and initial_last are not initialized, but if they would you might return with nothing.
hello, I am finding mid by reference.
 

Related to Find p in a Sorted Array with Unique Property | O(log n) Algorithm

1. What is the unique property of the sorted array that allows for an O(log n) algorithm to find p?

The unique property of the sorted array is that each element is greater than the previous element. This allows for a binary search approach to finding p, reducing the time complexity to O(log n).

2. How does the O(log n) algorithm for finding p work?

The algorithm starts by comparing the element at the middle index of the array to p. If it is equal, p is found. If it is greater than p, then the algorithm will search the left half of the array. If it is less than p, then the algorithm will search the right half of the array. This process is repeated until p is found or the entire array is searched.

3. What is the time complexity of the O(log n) algorithm for finding p?

The time complexity of the O(log n) algorithm for finding p is O(log n). This means that the time it takes to find p increases at a slower rate than the size of the array. For example, if the array size doubles, the time it takes to find p will only increase by one step.

4. How does the O(log n) algorithm for finding p compare to other algorithms?

The O(log n) algorithm for finding p is one of the most efficient algorithms for this task. It is faster than linear search, which has a time complexity of O(n). It is also faster than other logarithmic algorithms, such as interpolation search, which has a time complexity of O(log log n).

5. Can the O(log n) algorithm for finding p be used for arrays with non-unique elements?

No, the O(log n) algorithm for finding p only works for sorted arrays with unique elements. If the array contains duplicate elements, the algorithm may not be able to determine the correct position of p and may return the wrong index.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
949
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
12
Views
2K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
17
Views
2K
  • Programming and Computer Science
Replies
10
Views
3K
Back
Top