Let n be the length of the array.
1. If the middle element is equal to its index return success.
2. If the middle element is greater than its index search the left
half, since all the elements to its right will be greater than or
equal to it and hence cannot be equal to their index.
3. Else search
OK , I see . Thank you Dave
2010/11/3 Dave
> @Vaibhav: Your array doesn't work, because the problem statement says
> that the array elements are distinct, but 2 is not distinct in your
> array.
>
> Elaborating on how to decide whether to look to the left or right, if
> A[i] < i, look to the
Thanks Dave for the clarification. It works
On Wed, Nov 3, 2010 at 7:20 PM, Dave wrote:
> @Vaibhav: Your array doesn't work, because the problem statement says
> that the array elements are distinct, but 2 is not distinct in your
> array.
>
> Elaborating on how to decide whether to look to t
@Vaibhav: Your array doesn't work, because the problem statement says
that the array elements are distinct, but 2 is not distinct in your
array.
Elaborating on how to decide whether to look to the left or right, if
A[i] < i, look to the right, while if A[i] > i, look to the left.
Dave
On Nov 3,
Hi Dave,
How can we do a binary search on this array by using the function:
Let f(i) = A[i] - i
Please elaborate. I mean how can we take a decision whether to look into
left or right.
For example -> Pick array {1,2,2,4,5,6,8}
Vaibhav
On Wed, Nov 3, 2010 at 6:44 PM, Dave wrote:
> @Lichenga24
@Lichenga2404: Assuming that the array is sorted into increasing
order:
If A[1] > 1 or A[n] < n, return false.
Let f(i) = A[i] - i. Do a binary search to find i such that f(i) = 0.
If such an i is found, return true; else return false.
Binary search is O(log n). It works because f(i) is an increas
