Re: [algogeeks] finding element in rotated array
yes ..u r right ...thnks... -- 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] finding element in rotated array
how to find distortion using binary search?? On Sat, Jul 30, 2011 at 11:34 AM, Mohit Goel mohitgoel291...@gmail.comwrote: yes ..u r right ...thnks... -- 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] finding element in rotated array
Look for the spike...that is the index where the sorted property is disturbed. On Sat, Jul 30, 2011 at 11:44 AM, tech rascal techrascal...@gmail.comwrote: how to find distortion using binary search?? On Sat, Jul 30, 2011 at 11:34 AM, Mohit Goel mohitgoel291...@gmail.comwrote: yes ..u r right ...thnks... -- 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. -- 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] finding element in rotated array
low =lower_bound , high=upper_bound;
int a=arr[low];
while(lowhigh)
{
mid=(low+high)/2;
if( arr[mid]a midupper_bound arr[mid+1] a)
break; //you found the index of distortion
if(arr[mid]a)
low=mid+1;
else high=mid-1;
}
On Sat, Jul 30, 2011 at 11:46 AM, saurabh singh saurab...@gmail.com wrote:
Look for the spike...that is the index where the sorted property is
disturbed.
On Sat, Jul 30, 2011 at 11:44 AM, tech rascal techrascal...@gmail.comwrote:
how to find distortion using binary search??
On Sat, Jul 30, 2011 at 11:34 AM, Mohit Goel
mohitgoel291...@gmail.comwrote:
yes ..u r right ...thnks...
--
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.
--
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.
--
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] finding element in rotated array
above is when the sorted array is in increasing order.
On Sat, Jul 30, 2011 at 11:56 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
low =lower_bound , high=upper_bound;
int a=arr[low];
while(lowhigh)
{
mid=(low+high)/2;
if( arr[mid]a midupper_bound arr[mid+1] a)
break; //you found the index of distortion
if(arr[mid]a)
low=mid+1;
else high=mid-1;
}
On Sat, Jul 30, 2011 at 11:46 AM, saurabh singh saurab...@gmail.comwrote:
Look for the spike...that is the index where the sorted property is
disturbed.
On Sat, Jul 30, 2011 at 11:44 AM, tech rascal techrascal...@gmail.comwrote:
how to find distortion using binary search??
On Sat, Jul 30, 2011 at 11:34 AM, Mohit Goel
mohitgoel291...@gmail.comwrote:
yes ..u r right ...thnks...
--
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.
--
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.
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
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.
[algogeeks] finding element in rotated array
Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array You may assume that the array was originally sorted in increasing order EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array) -- 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] finding element in rotated array
find the distrotion first in the array using binary search . now you have the last element where the array was rotated. So pick your range, it will be either left or right subarray. Binary search in that. log(n). On Sat, Jul 30, 2011 at 11:01 AM, Mohit Goel mohitgoel291...@gmail.comwrote: Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array You may assume that the array was originally sorted in increasing order EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array) -- 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] finding element in rotated array
but this works ,if array is rotated multiple times ,around different pivots. -- 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] finding element in rotated array
it's rotation right , so no matter how many times you rotate , it will sorted except for one distortion. no ? On Sat, Jul 30, 2011 at 11:12 AM, Mohit Goel mohitgoel291...@gmail.comwrote: but this works ,if array is rotated multiple times ,around different pivots. -- 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.
