Let A be a 1- dimensional array with integers and "min" , "max", "number"
three integer numbers. find an algorithm that answers, if the value "number" is in the array e.g a [i] = number for some i, 1<= min <= i <= max <= n, and the complexity of the algorithms must be O(lgn)

I need some help on that! Thanks in advance!

The existence of max and min should not effect the problem, so you may as well answer the problem of finding an algorithm to determine if "number" is in the array of length with (time) complexity (or are we after the average complexity over all possible max and min?)

CB

__________________
Truth does not change because it is, or is not, believed by a majority of the people.

Giordano Bruno

hmmmmm......
The solution,(the algorithm) sould be implemented via a function (in a programming concept) and min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise. If the array was sorted, its binary searching that works. But the array is not sorted.
about the last question: hmm it talks about time complexity and not average time complexity...But its a good question anyway..I had not thought about that at all !
Thanks for your reply..it helps me.

Your explanation made it foggier.

"min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise."

array[10][30][20][40][60][70]
Function MMN( min=13, max=37, num=60)

Should the function check for values outside the given minimum and maximum arguments?
I do not understand the reason for min/max being arguments to the function if you only want to know whether the number is in the array.

Because the function may search in a sub array of the array.
Min max define the sub array.
In your example array[10][30][20][40][60][70]
10 is the first and 70 is the last. And there are 6 elements. If min = 1 and max = 6 and number is 20 function returns 1. Is there. But if min = 5 and max = 6 and number = 20 then function returns 0.Is not in that sub-array. But the worst (most difficult) case is for min = 1 and max = 6. Because the sub array in this case is the array. And the time complexity is dominated by this case.

Which is why they are irrelevant for a worst case complexity since this must occur when min=1 and max=n

CB

__________________
Truth does not change because it is, or is not, believed by a majority of the people.

Giordano Bruno

I agree..I have bad news..
The reason that i post this, was that my believe was that the question is wrong. You cant make an algorithm that it works in O(lgn) if the array is not sorted. (Beacause you must check all the elements, if the array is not sorted) And today i learned that this is true. I had asked if the question was wrong and if should be given that array is sorted, and they ansewred you must deal with the general case. But today i asked again and...
ok...
aidan, CaptainBlack,sorry and
MANY THANKS!!
Thank you guys.

If the list is sorted then binary search should do this in O(ln(n))

CB

__________________
Truth does not change because it is, or is not, believed by a majority of the people.

Giordano Bruno