O(log n) algorithm

[itseeker87]

Hi,

I have a problem at hand and i kinda need a head start in the same.

I have an array with some values inside and basically i need to check if the array (index value+1) == the actual value in that index and if so, i need to increase a counter.

int a[] = {-1, 0, 2, 4, 5, 6, 7}

and the result shud be 4 for this because ther are 4 elements in this array which satisfy the condition... as, starting from index a[3] till a[6]....the value of index is equal to (index+1)

like a[3] = 4
a[4] = 5
a[5] = 6
a[6] = 7

but the catch is to do it in O(log N)...and not o(n).....can someone plz gimme a head start into solving this problem??

thnx in advance...

[_uj]

but the catch is to do it in O(log N)...and not o(n).....can someone plz gimme a head start into solving this problem??

I suspect there exists no O(log N) solution. Say your array is,

1 2 3 4 5 6 7

This means all elements satisfy their positions and the count is 7. There's no way you can establish that without actually visiting all elements. So the worst case, when all elements satisfy, is O(N).

There is one way to speed up the the algoritm though. It assumes the array is sorted. If you use a divide and conquer approach you can divide up the array in subranges by sucessively halving the ranges. This is the same approach as in a binary search, but you cannot always discard the left or right subrange.

You know whether you can discard a subrange by comparing it to the corresponding range in this imaginary array,

1 2 3 4 5 6 7 ...... N

Say you have this array

-1 -1 0 1 1 4 5

and want to establish whether this subrange (within []) can be discarded

-1 [-1 0 1 1] 4 5

Then you just compare it to the corresponding range in the imaginary array,

1 [2 3 4 5] 6 7 ...... N

And yes you can discard it because the ranges don't overlap (and you only have to compare the leftmost and rightmost elements to establish that because the ranges are sorted).

---

Whether this effort is worthwhile depends very much on the composition of the array, and it's still O(N) in the worst case (when all elements are in their correct positions so you will never be able to discard any range).

[itseeker87]

hey...i get wat ur sayin...but i think i failed to explain the question correctly....

sorry for the confusion earlier....

ONE important point to note is that the array is alwayz assumed SORTED...in ascending order....

This being the case... is it possible to reach (log n)... i do understand that there is a need to go thru the entire array to arrive at a result(thats the obvious algo which i d think of)....but the specs given for this assignment is that it has to be done in O(log n)....

let me give a more clearer view to the problem, i hav not been explicit , i am sorry...

Suppose there is some number N, and there are 7 elements in another array. Each element in the array is given another spl number(one number per element)....say K ...then we hav to form the array by adding the first given value of N (-100) to the spl number K for first array(A) element. The resultant value is the first value of our input array(B). and this value now replaces for the new N. The 2nd element of the input array(B) = first value of array(B) + spl number K for 2nd element of array(A) and so on...

eg. N = -100 (intial value)
Array A: {99, 1, 2, 2, 1, 1, 1} [differnt K values]

then array B becomes

{ -1, 0, 2, 4, 5, 6, 7}.... [explanation -100 + 99 = -1 ---> -1 + 1 = 0---> 0+2= 2---->2+2 =4 ---->4+1=5---->5+1=6--->6+1=7 ]

it is this array that we have to chk for the condition i posted earlier... (index+1 = value of index)

At any point of time we can find the array A values for each array B value by subtracting the 2 adjacent index values...i was able to infer this now...does this help with a solution?

Given this... is it now possible to compute in O(log n) ???

[ProgramThis]

Yes, as _uj as already given you the answer and solution: it is possible to perform O(log(n)) run time search on an array that is "assumed" sorted (as you say).

You do exactly what _uj said and perform a "divide and conquer" approach by first checking the middle element and going from there. I won't reiterate what _uj has already spent the time to explain to you. Try rereading his post and trying out what he is saying.

[_uj]

Can help with extending this further please?

When doing a binary search you're successively halving the range of the array and each time selecting either the left or the right to proceed with.

In this case it's not always possible to discard one of the two halves. If not you need to save one for the time being and continue with the other. One way to do this is to make recursive calls.

As the halving of subranges proceeds you'll eventually find subranges that are just 2 or even 1 element wide. That's when the halving ends and you actually check whether elements are at the right position or not.

So use recursion to implement the successive halving. The recursion stops when a range holds just 1 or 2 elements. Then it's established whether you should increment the counter or not.

The reason I don't belive this algoritm has O(log N) complexity is that you cannot always discard one of the range halves (like you can in a binary search which is O(log N)). In the worst case, when all elements are at the right positions, you cannot discard a single range and all elements must be visited, typical of an O(N) algoritm. To perform better the algoritm depends on the elements to be such that many ranges can be discarded. And the wider they are when discarded the better.

[ProgramThis]

The reason I don't belive this algoritm has O(log N) complexity is that you cannot always discard one of the range halves (like you can in a binary search which is O(log N)). In the worst case, when all elements are at the right positions, you cannot discard a single range and all elements must be visited, typical of an O(N) algoritm. To perform better the algoritm depends on the elements to be such that many ranges can be discarded. And the wider they are when discarded the better.

You are absolutely correct: if we cannot assume that everything to the left/right of a correct value is correct (same as the index+1) for every value to the end of the array (either left or right) then it cannot be O(log(n)).

EX
{7 4 3 4 5 9 8}
Where the 3 4 5 in the middle are correct and the ends are incorrect you would have to visit every element in order to complete this search.

It is not so much of being able to "discard" half every time so much as either discarding OR including an entire half each time. I think that we are not getting all of the information for this assignment.

[_uj]

EX
{7 4 3 4 5 9 8}
Where the 3 4 5 in the middle are correct and the ends are incorrect you would have to visit every element in order to complete this search.

Note that the above is an invalid input array. Arrays are considered always sorted.

[_uj]

this is the entire spec.

The key is in the id numbers, like

99, 1, 2, 2, 1, 1, 1,

If they're all greater than 0 then the array elements will always form three sections in the array,

[losers][winners][losers]

In your example it becomes,

[-1, 0, 2] [4, 5, 6] []

(Any section can be empty)

In the first loser section the elements are smaller than the indexes, in the winner section they're equal, and finally in the last loser section they're larger.

The algoritm now must find the two borders between the winner section and the loser sections. And that can be done in O(log N). It's two binary searches finding the upper and lower border respectively.

Again note that the formation of three sections depends on all id numbers being greater than 0.

Examples,

1. {-1,0,1,2,4,5,6,7}

[-1,0,1,2,4,5,6,7] [] []

2. {-1,2,3,8,11,15}

[-1,2] [3] [8,11,15]

[Norm]

Have you found the algorithm yet?
Will you post it when you do?

[ideru]

are trying to compute the running time for the search?

if you want to get the O(log n) running time for a search algorithm, you need to get to know BST ( Binary Search Tree )

or generally a search using a TREE data structures.

BST on the average runs O(log n)

[itseeker87]

No, given to me is an array and i have to work with it to arrive at the solution using O(log n). Binary search is the right way. Howeve , my algorithm is jusy not complete as yet. I know, i am half way through and correct, but from there on i am a bit confused.

For now, i am able to compute the first index value upon sucessful decreasing(/2) where array[mid] is equal to mid+1 . But I neeed to continue this procedure ...i am wondering how so?

{-1,0,1,4,5} This for now will trace out that 4 is the answer which is true. But 5 is also an answer. But I dont know how to continue doing so? help please..

[_uj]

{-1,0,1,4,5} This for now will trace out that 4 is the answer which is true. But 5 is also an answer. But I dont know how to continue doing so? help please..

I don't quite know what's the remaning problem. If it's the binary search I suggest you start from a working algoritm, like this for example,

http://www.leepoint.net/notes-java/a...arysearch.html

and modify the condition where it's decided whether to continue with the left or right partition, to suit your situation.

As I said in my previous reply you need to make two binary searches, one for the lower bound and one for the upper bound of the winner's section in the array.

You could find the left bound in one binary search and then just iterate towards the upper bound but that would turn the algoritm into an O(N) one.

One binary search is O(log N) and two binary searches still are O(log N) so that's the way to go. You can avoid the second binary search though if you can establish that a winner found in the first search is a sole winner. You do that by checking whether the rightside neighbour is a loser. That would still give you O(log N).

Well, I guess you could combine the two binary searches into one but that's a much bigger challenge than to just modify the range spliting criterion in a standard binary search.

[ideru]

i agree with _uj

first try to create the BST then do a search right and left ..

you can create a node base on the index or make a node with the value and the index

and when you traverse your tree , compare the value of the index and IndexValue if it satisfy your condition , then OK..

[seeguna]

Hi Guys,
Using Binary Search we can easily achieve it within 0(logn) time...

I will paste the sample code....(Dont worry that , for each and every element searching is done)...

private static void binarySearch(int[] a, int low, int high) {
int mid = (low+high) /2;
if(a[mid]==mid+1){
System.out.println(" Equal element are :" + a[mid]);

}
if(a[mid]>a[low]){
binarySearch(a,low,mid-1);
}
if(a[mid]<a[high]){
binarySearch(a,mid+1,high);
}

}

u can make a call frm main function by using the following stmt:-
binarySearch(a,0,a.length-1);

Note :a [] is the array which contains all values

[ProgramThis]

i agree with _uj

first try to create the BST then do a search right and left ..

you can create a node base on the index or make a node with the value and the index

and when you traverse your tree , compare the value of the index and IndexValue if it satisfy your condition , then OK..

There is absolutely no need for a BST here. As seeguna has shown you can perform O(log(n)) searches on arrays given the conditions of the problem easily. Complicating the issue with trees is not the solution.

@ itseeker87
You should really read up on Divide and Conquer algorithms.

For now, i am able to compute the first index value upon sucessful decreasing(/2) where array[mid] is equal to mid+1 . But I neeed to continue this procedure ...i am wondering how so?

Lets say we have the following array:

[-1 0 3 4 8 9 10 11 12]

You find that the middle element is 8 where the index is 5. Obviously everything, as you have said, above and including 8 is not valid. Then you make the call to the lower half and EXclude the upper half (i.e. do not even bother calling the recursive method on the upper half).

The search then goes on:
[-1 0 3 4]

Depending on how your algorithm works (i.e. how you chose the middle element when there is an even number) you would chose either 0 or 3 as your middle element (usually the 3).

So we have 3 = index which is 3. We now know that everything above the 3 is good, and possibly the stuff below is good as well. You will need to append everything after the 3 to a recursive call on the front half of the array. We have:

[-1 0]

The "middle" element is 0 != index+1 therefore we know that all elements before it are excluded and we make a call on the rest of the array, which is []. The IF condition (terminating condition) will pick up the empty array and return.

NOW, that being said, if this is not even a possible solution, meaning that you will NEVER have a set of elements in the middle of the array that are valid where the elements on the ends are NOT valid then this is even easier.