How can I find if a sorted array has an element a[j]=j in O(log n) time?(no duplicates)
+12
A:
If the array is of integers and cannot contain duplicates, you can just use binary search.
E.g. let's say we have the array:
a[0] == -30
a[1] == 1
a[2] == 200
a[3] == 200
a[4] == 204
a[5] == 205
a[6] == 206
a[7] == 207
- First try a[floor(avg(0,7))] (i.e. a[3]). This equals 200. 200 is too big.
- So move to the lower half. Try a[floor(avg(0,2))] (i.e. a[1]). This equals 1. Hurray!
Your binary search will either successfully find some j for which a[j] == j, or it will fail by running out of places to look. Since a binary search is O(log n), you will know within that time complexity the value of j or that no such j exists.
Note that if multiple values of j satisfy the condition, you will just find an arbitrary one of them.
Jon Rodriguez
2010-10-28 01:12:57
@Manish, please update your question. We are not sure what you are asking.
BobbyShaftoe
2010-10-28 01:26:32
I thought of Binary search too by seeing log n .But imagine a scenario like this a[0]=0 a[1]=1 a[2]=2 a[3]=3 a[4]=4 a[5]=5 a[6]=6 a[7]=7 .Now if I started from a[4] I cant say that only 1 direction will have solution .Here both of them do ....I mean that I cannot always cut the input by half. But yeah if only one such instance is asked then I can say I have log n algo.
Manish
2010-10-28 01:30:58
@Manish, I am assuming that the OP means "does there exist any j for which a[j] == j"
Jon Rodriguez
2010-10-28 01:32:54
@Manish: In that case when you find a[4] = 4 you're done. You have determined that there is in fact a j such that a[j] = j, and in that particular case you've done it in O(1) time which is also O(log n) time.
andand
2010-10-28 01:37:42
@Jon ..Yes it does.
Manish
2010-10-28 01:38:33
@Manish Note that user434507 's answer is correct in pointing out that binary search might not work if the array is allowed to contain duplicates or floats.
Jon Rodriguez
2010-10-28 01:43:20
@Jon, agreed, I was going to say that this algorithm only works for an array of integers.
LarsH
2010-10-28 02:20:10
-1 doesn't work -- consider what happens if every element in your array is 7 initially.
Chris Dodd
2010-10-30 02:04:59
+8
A:
If it can contain duplicate values, or it is a floating point array, you can't. Counterexample: a[2k]=2k+1, a[2k+1]=2k+1 or 2k+2. Worst case scenario, you have to check a[2k+1] for all k.
If it is an integer array and all values are distinct, then you do binary search. Look at a[1]-1 and a[n]-n. If they are the same sign, the answer is no. If they have different signs, look at a[n/2]-n/2. It's either zero (and then you have your answer), or one of the intervals (1,n/2) or (n/2,n) will have different signs at the ends. Take that interval and repeat.
Could you please provide two separate counterexamples for the cases where a can contain duplicates and where a can contain floats?
Jon Rodriguez
2010-10-28 01:24:21
The counterexample for floats is a[2k]=2k+0.5, a[2k+1]=2k+1 or 2k+2. The point is that the binary search will only work if we're looking for a single solution or a contiguous array of solutions. If the array can contain floats or duplicates, there may be as many as n/2 disjoint solutions, and we may have to check them all by hand.
2010-10-28 01:35:24
Ah, I understand now. Upvote. However, it might be a lot easier for visual learners like me to understand if you would provide full examples depicting an entire array rather than just two elems.
Jon Rodriguez
2010-10-28 01:40:27
+1
A:
Assuming duplicates are disallowed:
#include <stdio.h>
int
find_elt_idx_match( int *a, int lo, int hi )
{
int elt, idx;
while ( lo <= hi )
{
idx = lo + ( hi - lo ) / 2; /* Thanks, @andand */
elt = a[ idx ];
if ( elt == idx )
{
return 1;
}
if ( elt < idx )
{
lo = idx + 1;
}
else
{
hi = idx - 1;
}
}
return 0;
}
int
main( void )
{
int a[ 100 ];
/* fill a */
/* ... */
printf( "idx:elt match? %c\n", find_elt_idx_match( a, 0, 99 ) ? 'y' : 'n' );
return 0;
}
William
2010-10-28 02:20:48
There you go +1, except what's up with the 1970s-style function notation?
David Titarenco
2010-10-28 02:45:14
Not to nit-pick, but idx = ( lo + hi ) / 2; can overrun the range of ints. Better to use idx = lo + (hi - lo) / 2; (ref: http://en.wikipedia.org/wiki/Binary_search_algorithm#Computer_usage)
andand
2010-10-28 03:22:26
@David: Not sure what you mean. `printf()` vs. `cout`? I intended only C, not C++.
William
2010-10-28 08:52:35
@William I think he means the indentation of braces and blocks (2 spaces for a brace, then two more for the block)
Adriano Varoli Piazza
2010-10-28 12:25:25
@William: no no, I was talking about `[type]\newline[function name]` :P but I exaggerated the time frame
David Titarenco
2010-10-28 19:21:02
A:
public int getFirstMatchedIndex(int[] oArry)
{
int i = 0;
while(i < oArry.Length )
{
if (oArry[i] == i)
return i;
else if (oArry [i] > i)
i=oArry [i];
else
i++;
}
return -1;
}
Mouadh
2010-10-28 12:17:16
A:
If duplicates are not allowed, and your list is sorted according to obvious order a[i] < a[i+1] (strictly less, not equal!), then it is also true that a[i]-i < a[i+1] - i, so it follows that a[i]-i <= a[i] - (i+1). (Note the inequality becomes "<=".) In other words, the values of a[i]-i, throughout your list, are in order. Search for the value 0=a[i]-i, using binary search on a sorted list.
Josephine
2010-10-30 01:42:22