+1 Gene
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Wed, Sep 28, 2011 at 1:36 AM, Gene wrote:
> Indeed you must be given that all the array elements are unique or at
> least that there are no more than floor(n/2) repeats). Otherwise this
> is impossible. The
Indeed you must be given that all the array elements are unique or at
least that there are no more than floor(n/2) repeats). Otherwise this
is impossible. The simplest way to think about it is first to search
for i such that a[i] > a[i+1]. At that point you know there are two
sorted ranges a[0]..
first find the place where the mismatch occours in the array linearly ..
like if the the array is in increasing sorted order than first find a
location where it violates this property
{8,9,18,19,22,25,36,2,3,5,6,7};
the property is violated at index 7
now u have 2 sorted arrays from index [0-6] a
Rotated array => [ 0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0 ]
find 1 using binary search ...
turns out we cant use binary search if we've repeated elements in rotated
array ...
~raju
On Tue, Sep 27, 2011 at 8:18 PM, akanksha wrote:
> /*
> A program in which an array have an increasing sequence and
/*
A program in which an array have an increasing sequence and an
decreasing sequence .
in these array search an element in o(n)time complexity
these is also called rotated array
*/
#include
#include
#include
using namespace std;
void search(int *array,int intial_index,int last_index,int ele);
int
Very sorry the mistake. I'm not familiar with your name, and few
computer science students where I live are women.
The first detail is that binary search will only work if you assume no
duplicates. This is easy to see if you envision an input that is all
1's except for a single 2. In order to d
check out this link guys,,, for more implementation details
On Sun, Aug 8, 2010 at 7:59 PM, ashita dadlani wrote:
> first of all Gene..this is not "he" but "she" :P
> and secondly,can you please mention the details you are talking about so
> that we can reach to a solution?
>
>
> On Sun, Aug 8,
first of all Gene..this is not "he" but "she" :P
and secondly,can you please mention the details you are talking about so
that we can reach to a solution?
On Sun, Aug 8, 2010 at 7:48 PM, Gene wrote:
> Well, then, you must say that in the problem! To to find k, ashita
> dadlani's solution works
Well, then, you must say that in the problem! To to find k, ashita
dadlani's solution works fine, except he has left out important
details. This binary search is a bit tricker that the one to find a
value.
On Aug 8, 2:34 am, Manjunath Manohar wrote:
> hey wait a sec,.. we wont be given the k va
its possible.first apply binary search to find the index where the array is
rotated.
eg.a=[8,9,1,2,3,4,56,7]
first apply binary search to find the value i=2.
now we have 2 sub sorted arrays,ie, from i=0 to i=1 and from i=2 to i=8.
apply binary search to these sub sorted arrays each of which will ta
hey wait a sec,.. we wont be given the k value..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroup
On Aug 7, 4:41 pm, AlgoBoy wrote:
> is there a way to apply a binary search on a sorted array...with a
> catch... the array is rotated k times clockwise
>
> Example...4,5,1,2,3...
>
> I heard a binary search is possible..
Of course it's possible. If the array A has N items, then just
replace eve
12 matches
Mail list logo
