Solve this algorithm ?!!

[algo_man]

We need an algorithm that search an element x in an array A[1..n] but with a O(1). this element neither maximum nor minimum ????

Could you explain that ?

[Rashakil Fol]

With no further information about the element or the array, you can't.

[Infarction]

I'd say you'd be using the array as a hash table. Sorry for digging up a 4-day old thread ;)

[joshuatree]

O(1) == constant. Infarction was right tho, we need more info...
All we know from your explanation, is that the list appears to be ordered from 1..n. and that u want to be able to investigate the number held at a position in the array. True?
a single comparison at a known index is constant time.

[Czarina Bayena]

hi! I am a new member here. And still learning algorithm. Can you pls explain how to solve the problems below. please? I need some help. And yours will be highly appreciated. Thank you. :)

1.Write an algorithm that outputs the index of the last occurrence of the value key in the sequence a1,...,an. If key is not in the sequence, the algorithm outputs the value 0.

2.Write an algorithm that outputs the index of the first item that is greater than its predecessor in the sequence a1,...,an. If the items are in nondecreasing order (example: ai ≤ ai+1, for i=1, ..., n-1), the algorithm outputs the value 0.

[Momerath]

1.

Set result = 0
for each element in sequence A1..An, in reverse order, do
    if current element = key then
        set result = current index
        exit for loop
    end if
end for
output result

2.

set result = 0
for each element in sequence A1..An-1 do
    if current element > next element then
        result = current index
        exit for loop
    end if
end for
output result

[arkoenig]

The problem is vaguely specified, so I am going to try to do some guessing at how to specify it more precisely. This guessing is based on the assumption that the problem actually has a solution--in other words, that there exists an algorithm capable of solving it in O(1) time.

My first observation is that such an algorithm cannot possibly inspect every element of the array, because doing that for an n-element array would require O(n) time. So after a little head-scratching, I think that the original problem is probably the following:

Define the maximum element of an array, if such an element exists, as the unique element that is strictly greater than every other element. Note that an array with no elements has no maximum, and similarly, an array with two or more equal elements that are strictly greater than all the other elements also has no maximum. This definition is consistent with common mathematical usage, which uses the term "maximal" to refer to elements that might not be unique, and "maximum" to carry the implicit claim of uniqueness.

Define the minimum element, if one exists similarly: the unique element that is strictly less than all the other elements.

With these definitions, every array with three or more elements has at least one element that is neither the maximum nor the minimum. For an array with two elements, both elements satisfy this condition if they are equal; neither of them satisfies if they are not.

I am guessing that the original question should be interpreted this way: Given an array, find an element, if one exists, that is neither the maximum nor the minimum, and do so in O(1) time. This problem has a solution, which I will leave as an exercise :-)