@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 >>>>> <[email protected]>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 >>>>>> <[email protected]>wrote: >>>>>> >>>>>>> n=sizeof(arr); >>>>>>> n--; >>>>>>> >>>>>>> while(n) >>>>>>> { >>>>>>> if(elem=arr[n]) >>>>>>> print found; >>>>>>> >>>>>>> n--; >>>>>>> >>>>>>> } >>>>>>> >>>>>>> On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר <[email protected]> >>>>>>> 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 [email protected]. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> [email protected]**. >>>>>>>> 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 [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]**. >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]**. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]**. >>>>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
