[algogeeks] Re: Search an array of unknown length
nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
@saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.com wrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
Well sir I am fully aware why this is hapening.Kindly reread what I wrote .*what if we are given only the address of the array.* I personaly feel anyone who asked the question never expected this to be the answer.(using sizeof). On Tue, Aug 23, 2011 at 2:42 PM, sagar pareek sagarpar...@gmail.com wrote: @saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.comwrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
hmm ok my mistake of reading On Tue, Aug 23, 2011 at 6:56 PM, saurabh singh saurab...@gmail.com wrote: Well sir I am fully aware why this is hapening.Kindly reread what I wrote .*what if we are given only the address of the array.* I personaly feel anyone who asked the question never expected this to be the answer.(using sizeof). On Tue, Aug 23, 2011 at 2:42 PM, sagar pareek sagarpar...@gmail.comwrote: @saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.comwrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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
Re: [algogeeks] Re: Search an array of unknown length
@dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
[algogeeks] Re: Search an array of unknown length
If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
Just a small code to back up my point... http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
@dave may be its a bit offtopic,(and may be stupid) but if the numbers are in a small range (say 1 to 1000) isn't the probability that the absolute garbage value would be greater than the array elements(assuming garbage to be bits of random 0's and 1's)?Assuming we have not entered into some other valid memory area.Can't this fact be used to produce a solution that's valid for most of the cases? On Sat, Aug 20, 2011 at 12:21 AM, sagar pareek sagarpar...@gmail.comwrote: thanks for pointing it out On Sat, Aug 20, 2011 at 12:16 AM, Dave dave_and_da...@juno.com wrote: @Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
[algogeeks] Re: Search an array of unknown length
@Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
Well in that case additive approach will work. Sanju :) -- 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.
[algogeeks] Re: Search an array of unknown length
@Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
Re: [algogeeks] Re: Search an array of unknown length
thanks for pointing it out On Sat, Aug 20, 2011 at 12:16 AM, Dave dave_and_da...@juno.com wrote: @Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
