Well actually, I've just gone through Dave's code thoroughly and I believe
that his code is most appropriate.
Thanks viper11 for providing the explanation.
As for my code, I'd like to replace
while (i!=j)
with
while (i < j)
because != won't work for middle element if the number of elements are odd
... and it also won't work if the number of elements are even.
Anyway, thanks Dave for providing us with such a great solution. Please
keep posting! :-)
And others, thanks for pointing out the issue in my code.
On Sat, Oct 6, 2012 at 9:03 PM, Kalidhakani J <kanikali...@gmail.com> wrote:
> @umer - what if the element to be searched is at the middle of the array?
> your code doesn't handles this. check out.
>
>
> On Sat, Oct 6, 2012 at 3:38 AM, icy` <vipe...@gmail.com> wrote:
>
>> nice solution, Dave!
>>
>> @Umer -- if the sought ele is first, then Dave's code has it sitting in
>> the variable temp for a little while. Loop will stop when size is 0,
>> since arr[0]==elem. Now he throws temp back into arr[0], which will return
>> index 0 from the last compare line.
>>
>> On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
>>>
>>> @Dave Thanks for pointing that out.
>>>
>>> But I still can't get what if elem is on first element or it is not
>>> present in the array? How is your code going to handle that situation?
>>>
>>> @Atul, Well yes, In the given question, the number of iterations were
>>> 2n. Which I have reduced to n+n/2.
>>>
>>>
>>>
>>>
>>>
>>> On Tue, Oct 2, 2012 at 11:13 PM, atul anand <atul.8...@gmail.com> wrote:
>>>
>>>> @umer : how no. of comparison are reduced to half by moving both
>>>> sides....you have 2 if condition inside, so you are making 2
>>>> comparisons at each iteration + n/2 comparison for while loop so
>>>> number of comparisons are n+n/2
>>>>
>>>> On 10/2/12, Umer Farooq <the....@gmail.com> wrote:
>>>> > why don't we try it from both ends ... something like this:
>>>> >
>>>> > int i = 0; j = size-1;
>>>> >
>>>> > while (i != j)
>>>> > {
>>>> > if (arr[i] == elem)
>>>> > return arr[i];
>>>> > if (arr[j] == elem)
>>>> > return arr[j];
>>>> > }
>>>> >
>>>> > this way, we have eliminated half of the comparisons in for loop?
>>>> What do
>>>> > you guys say?
>>>> >
>>>> > On Tue, Oct 2, 2012 at 12:18 PM, rafi <rafiw...@gmail.com> wrote:
>>>> >
>>>> >> Vikas is right!
>>>> >> while (n) is equal to (while n!=0)
>>>> >> you have 2n compares!
>>>> >>
>>>> >> בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
>>>> >>
>>>> >>> still there is no improvement, compiler will generate the code to
>>>> >>> compare
>>>> >>> with zero here. what you have accomplished is , hide it from human
>>>> eyes
>>>> >>>
>>>> >>> On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
>>>> >>>>
>>>> >>>> @atul:
>>>> >>>> still it won't compare 0 th element. Slight modification in your
>>>> code:
>>>> >>>>
>>>> >>>> n=*sizeof(arr)*;
>>>> >>>> do
>>>> >>>> {
>>>> >>>> if(elem==arr[*--n*])
>>>> >>>> print found;
>>>> >>>>
>>>> >>>> }while(n);
>>>> >>>>
>>>> >>>> On Mon, Oct 1, 2012 at 9:50 AM, atul anand <atul.8...@gmail.com>
>>>> wrote:
>>>> >>>>
>>>> >>>>> yes, but there no need of checking outside the loop
>>>> >>>>>
>>>> >>>>> n=sizeof(arr)-1;
>>>> >>>>> do
>>>> >>>>> {
>>>> >>>>> if(elem==arr[n])
>>>> >>>>> print found;
>>>> >>>>> n--;
>>>> >>>>>
>>>> >>>>> }while(n);
>>>> >>>>>
>>>> >>>>>
>>>> >>>>>
>>>> >>>>> On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
>>>> >>>>> <algorit...@gmail.com>wrote:
>>>> >>>>>
>>>> >>>>>> @atul: keep one more checking outside loop for element at 0 th
>>>> index.
>>>> >>>>>> Because when n = 0 the your loop come out from the loop without
>>>> >>>>>> comparing
>>>> >>>>>> it.
>>>> >>>>>>
>>>> >>>>>>
>>>> >>>>>> On Mon, Oct 1, 2012 at 8:55 AM, atul anand
>>>> >>>>>> <atul.8...@gmail.com>wrote:
>>>> >>>>>>
>>>> >>>>>>> n=sizeof(arr);
>>>> >>>>>>> n--;
>>>> >>>>>>>
>>>> >>>>>>> while(n)
>>>> >>>>>>> {
>>>> >>>>>>> if(elem=arr[n])
>>>> >>>>>>> print found;
>>>> >>>>>>>
>>>> >>>>>>> n--;
>>>> >>>>>>>
>>>> >>>>>>> }
>>>> >>>>>>>
>>>> >>>>>>> On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר <rafiw...@gmail.com>
>>>> >>>>>>> wrote:
>>>> >>>>>>>
>>>> >>>>>>>> Hi
>>>> >>>>>>>> i was in an interview and was given a simple function
>>>> >>>>>>>> int arrExsits(int* arr,int size,int elem){
>>>> >>>>>>>> for (int i=0;i<size;++i)
>>>> >>>>>>>> if(elem==arr[i])
>>>> >>>>>>>> return i;
>>>> >>>>>>>> return -1;
>>>> >>>>>>>> }
>>>> >>>>>>>> this function does 2n compares
>>>> >>>>>>>> n- the if statment
>>>> >>>>>>>> n-check that i is smaller then size
>>>> >>>>>>>> i was suppose to give an optimal (less compares) solution so i
>>>> gave
>>>> >>>>>>>>
>>>> >>>>>>>> int arrExsits(int* arr,int size,int elem){
>>>> >>>>>>>> if (arr[size-1]==elem)
>>>> >>>>>>>> return size-1;
>>>> >>>>>>>> arr[size-1]=elem]
>>>> >>>>>>>> for (int i=0;;++i)
>>>> >>>>>>>> if(elem==arr[i]){
>>>> >>>>>>>> if (i!=size-1)
>>>> >>>>>>>> return i;
>>>> >>>>>>>> return -1;
>>>> >>>>>>>> }
>>>> >>>>>>>> this solution works and it has n+2 compares the first one
>>>> another n
>>>> >>>>>>>> and the second inner if.
>>>> >>>>>>>> they told me it's good (and I've passed) but they told just
>>>> for my
>>>> >>>>>>>> knowledge that there is a better N compare solution.
>>>> >>>>>>>> I've searched the web but couldn't find it.
>>>> >>>>>>>> anybody knows?
>>>> >>>>>>>> Thanks
>>>> >>>>>>>>
>>>> >>>>>>>> --
>>>> >>>>>>>> You received this message because you are subscribed to the
>>>> Google
>>>> >>>>>>>> Groups "Algorithm Geeks" group.
>>>> >>>>>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> >>>>>>>> To unsubscribe from this group, send email to
>>>> >>>>>>>> algogeeks+...@googlegroups.com****.
>>>> >>>>>>>> For more options, visit this group at
>>>> http://groups.google.com/**
>>>> >>>>>>>> group/algogeeks?hl=en<http://**groups.google.com/group/**
>>>> algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>>
>>>> >>>>>>>> .
>>>> >>>>>>>>
>>>> >>>>>>>
>>>> >>>>>>> --
>>>> >>>>>>> You received this message because you are subscribed to the
>>>> Google
>>>> >>>>>>> Groups "Algorithm Geeks" group.
>>>> >>>>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> >>>>>>> To unsubscribe from this group, send email to
>>>> >>>>>>> algogeeks+...@googlegroups.com****.
>>>> >>>>>>> For more options, visit this group at
>>>> http://groups.google.com/**
>>>> >>>>>>> group/algogeeks?hl=en<http://**groups.google.com/group/**
>>>> algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>>
>>>> >>>>>>> .
>>>> >>>>>>>
>>>> >>>>>>
>>>> >>>>>> --
>>>> >>>>>> You received this message because you are subscribed to the
>>>> Google
>>>> >>>>>> Groups "Algorithm Geeks" group.
>>>> >>>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> >>>>>> To unsubscribe from this group, send email to
>>>> >>>>>> algogeeks+...@googlegroups.com****.
>>>> >>>>>> For more options, visit this group at
>>>> http://groups.google.com/**
>>>> >>>>>> group/algogeeks?hl=en
>>>> >>>>>> <http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>
>>>> >
>>>> >>>>>> .
>>>> >>>>>>
>>>> >>>>>
>>>> >>>>> --
>>>> >>>>> You received this message because you are subscribed to the Google
>>>> >>>>> Groups "Algorithm Geeks" group.
>>>> >>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> >>>>> To unsubscribe from this group, send email to
>>>> >>>>> algogeeks+...@googlegroups.com****.
>>>> >>>>> For more options, visit this group at http://groups.google.com/**
>>>> >>>>> group/algogeeks?hl=en
>>>> >>>>> <http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>
>>>> >.
>>>> >>>>>
>>>> >>>>
>>>> >>>> --
>>>> >> You received this message because you are subscribed to the Google
>>>> Groups
>>>> >> "Algorithm Geeks" group.
>>>> >> To view this discussion on the web visit
>>>> >> https://groups.google.com/d/**msg/algogeeks/-/SwuLNscTCOoJ<https://groups.google.com/d/msg/algogeeks/-/SwuLNscTCOoJ>
>>>> .
>>>> >>
>>>> >> To post to this group, send email to algo...@googlegroups.com.
>>>> >> To unsubscribe from this group, send email to
>>>> >> algogeeks+...@**googlegroups.com.
>>>> >> For more options, visit this group at
>>>> >> http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>
>>>> .
>>>> >>
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > Umer
>>>> >
>>>> > --
>>>> > You received this message because you are subscribed to the Google
>>>> Groups
>>>> > "Algorithm Geeks" group.
>>>> > To post to this group, send email to algo...@googlegroups.com.
>>>> > To unsubscribe from this group, send email to
>>>> > algogeeks+...@**googlegroups.com.
>>>> > For more options, visit this group at
>>>> > http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>
>>>> .
>>>> >
>>>> >
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+...@**
>>>> googlegroups.com.
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>>
>>>>
>>>
>>>
>>> --
>>> Umer
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/MCOQyzdtcAMJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Umer
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
