@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.um...@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 <rafiwie...@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>
>>>>>>>> .
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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>
>>>>>> .
>>>>>>
>>>>>
>>>>> --
>>>>> 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 view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/SwuLNscTCOoJ.
>>
>> 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.
>
>
--
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.
