[algogeeks] Re: Give an efficient search algo
@Amit: It is given that the array is decreasing, then increasing. An array of constants is neither increasing nor decreasing. Dave On Aug 3, 11:41 pm, amit karmakar amit.codenam...@gmail.com wrote: Can you show how to find k for an array containing n 2's using binary search. On Aug 4, 6:29 am, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.-Hidequoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- 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: Give an efficient search algo
@Kartik: k can be found with a binary search. Once k is known, the key can be found with one or two binary searches. O(log n). Dave On Aug 3, 11:08 pm, kartik sachan kartik.sac...@gmail.com wrote: if k is known to us the searching can be done in log(n) time if k is not known to us ,we first find the k then solution in O(n) time correct me if i am worng... -- 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: Give an efficient search algo
@Tushar: Either value of k will work. You are going to search both sides of k. Dave On Aug 3, 10:59 pm, Tushar Bindal tushicom...@gmail.com wrote: if we do not know k, how do we find it? inthe series : 17 15 13 11 9 1 3 5 7 we can take k at element 1 also as the descending series can be 17 15 13 11 9 1 and ascending 3 5 7 OR descending 17 15 13 11 9 and ascending 1 3 5 7 isn't there any relationship in kth and (k+1)th element that helps us find out k correctly On Thu, Aug 4, 2011 at 7:37 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote: For question two , try this. see te element at arr[0] . and supose you have to find k . if arr[0]==k , then yes we found the element else see the diff betweem arr[0] and k. that will be minimum amount of steps needed to convert a[0] to k(let abs(a[0]-k) = p). then repeat the procedure again at the new element arr[p] untill you find the number of reach end of array.. On Thu, Aug 4, 2011 at 6:59 AM, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.-Hide quoted text - - Show quoted text - -- 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. -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- 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. -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : tushicom...@gmail.com Website:www.jugadengg.com- Hide quoted text - - Show quoted text - -- 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: Give an efficient search algo
Problem 2 can be solved in O(n/k). If you want to search for x, look at the first element. If the element is not found, find the difference between the current element and x, let this be stored in diff. Now, x will be atleast diff number of positions ahead in the array. So, the next position is current position + diff. If the element is still not found, continue. On Thu, Aug 4, 2011 at 5:27 PM, Dave dave_and_da...@juno.com wrote: @Amit: It is given that the array is decreasing, then increasing. An array of constants is neither increasing nor decreasing. Dave On Aug 3, 11:41 pm, amit karmakar amit.codenam...@gmail.com wrote: Can you show how to find k for an array containing n 2's using binary search. On Aug 4, 6:29 am, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.-Hidequoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- 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. -- Gaurav Menghani -- 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: Give an efficient search algo
@amit it's given that array is increasing then decreasing..so where there is change from incre to drece that value of i in loop will be k in this we can find out k if not given -- 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: Give an efficient search algo
@dave:how can we find value of 'k' in (log n) On Thu, Aug 4, 2011 at 5:41 PM, kartik sachan kartik.sac...@gmail.comwrote: @amit it's given that array is increasing then decreasing..so where there is change from incre to drece that value of i in loop will be k in this we can find out k if not given -- 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, Kamakshi kamakshi...@gmail.com -- 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: Give an efficient search algo
@Kamakshii: Do a binary search on a[i] - a[i-1]. If this is negative, i is in the decreasing range, i.e., i k, so reset the lower limit of the interval. If it is positive, i is in the increasing range, i.e., i k, so reset the upper limit of the interval. Quit when the interval length is 1. Let k be the lower limit of that interval. Then a[k] - a[k-1] 0, so a is decreasing at k, and a[k+2] - a[k+1] 0, so a is increasing at k+1. According to the problem statement, it is possible for a[k] to equal a[k+1]. In this case, a[0] to a[k] still is decreasing and a[k+1] to a[n-1] still is increasing, so this value of k works. Dave On Aug 4, 1:23 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @dave:how can we find value of 'k' in (log n) On Thu, Aug 4, 2011 at 5:41 PM, kartik sachan kartik.sac...@gmail.comwrote: @amit it's given that array is increasing then decreasing..so where there is change from incre to drece that value of i in loop will be k in this we can find out k if not given -- 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, Kamakshi kamakshi...@gmail.com -- 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: Give an efficient search algo
@Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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: Give an efficient search algo
Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.
Re: [algogeeks] Re: Give an efficient search algo
Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.
[algogeeks] Re: Give an efficient search algo
@Ankur: Not a rotated sorted array. The given array looks like a V, but the rotated sorted array would look like / / Dave On Aug 3, 2:52 pm, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.- Hide quoted text - - Show quoted text - -- 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: Give an efficient search algo
I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.
Re: [algogeeks] Re: Give an efficient search algo
@Dave ..for question 1 why use binary search for 1to k initially say array is 17 15 13 11 9 1 3 5 7 the kth element is 9 ..Now if u want to find 3 why to search in first half ..Just compare with kth element and if greater find on left else go to right :) Not totally conviced with ur solution for 1 st question though it will give answer but not optimized one :) On Wed, Aug 3, 2011 at 4:02 PM, amit karmakar amit.codenam...@gmail.comwrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.
[algogeeks] Re: Give an efficient search algo
But what if the kth element is the 1? That's permitted by the problem statement. And my solution is O(log n), which is of optimal order. Dave On Aug 3, 3:23 pm, Ankur Garg ankurga...@gmail.com wrote: @Dave ..for question 1 why use binary search for 1to k initially say array is 17 15 13 11 9 1 3 5 7 the kth element is 9 ..Now if u want to find 3 why to search in first half ..Just compare with kth element and if greater find on left else go to right :) Not totally conviced with ur solution for 1 st question though it will give answer but not optimized one :) On Wed, Aug 3, 2011 at 4:02 PM, amit karmakar amit.codenam...@gmail.comwrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.- Hide quoted text - - Show quoted text - -- 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: Give an efficient search algo
@Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.- Hide quoted text - - Show quoted text - -- 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: Give an efficient search algo
For question two , try this. see te element at arr[0] . and supose you have to find k . if arr[0]==k , then yes we found the element else see the diff betweem arr[0] and k. that will be minimum amount of steps needed to convert a[0] to k(let abs(a[0]-k) = p). then repeat the procedure again at the new element arr[p] untill you find the number of reach end of array.. On Thu, Aug 4, 2011 at 6:59 AM, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.- Hide quoted text - - Show quoted text - -- 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. -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- 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: Give an efficient search algo
if we do not know k, how do we find it? inthe series : 17 15 13 11 9 1 3 5 7 we can take k at element 1 also as the descending series can be 17 15 13 11 9 1 and ascending 3 5 7 OR descending 17 15 13 11 9 and ascending 1 3 5 7 isn't there any relationship in kth and (k+1)th element that helps us find out k correctly On Thu, Aug 4, 2011 at 7:37 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote: For question two , try this. see te element at arr[0] . and supose you have to find k . if arr[0]==k , then yes we found the element else see the diff betweem arr[0] and k. that will be minimum amount of steps needed to convert a[0] to k(let abs(a[0]-k) = p). then repeat the procedure again at the new element arr[p] untill you find the number of reach end of array.. On Thu, Aug 4, 2011 at 6:59 AM, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.- Hide quoted text - - Show quoted text - -- 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. -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- 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. -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : tushicom...@gmail.com Website: www.jugadengg.com -- 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: Give an efficient search algo
Can you show how to find k for an array containing n 2's using binary search. On Aug 4, 6:29 am, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.-Hide quoted text - - Show quoted text - -- 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.
