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!
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.
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.