@umer : also ur code wont work if the searching element is at the middle of the array...
On Tue, Oct 2, 2012 at 11:43 PM, atul anand <atul.87fri...@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.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. > > -- 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.