Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.
Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.
int findPivot(int arr[], int n)
{
int low = 0, high = n1, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(arr[low] < arr[mid])
low = mid + 1;
else if (arr[mid] < arr[high])
high = mid1;
else
return mid;
}
return 1;
}
Please suggest me ways in which i can modify this to work for finding
the pivot element.
Regards,
Rajesh 8 2034
Rajesh wrote: Question :An element in a sorted list can be found in O(log n) time via binary search. But suppose I rotate the sorted list at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated list in O(log n) time.
Once the position of the pivot element(least element)is known things will be easy. I'm not able to correct the following piece of code(which finds the pivot element's position) to make it work properly. Please suggest ways in which i can do it.
int findPivot(int arr[], int n)
I'd rather use
int findPivot (const int *arr, int size)
or even
size_t findPivot (const int *arr, size_t size)
{ int low = 0, high = n1, mid; while(low <= high) { mid = (low + high) / 2; if(arr[low] < arr[mid]) low = mid + 1; else if (arr[mid] < arr[high]) high = mid1;
Can this case occur?
else return mid; } return 1; }
Please suggest me ways in which i can modify this to work for finding the pivot element.
As I am not sure how much of this is homework:
 printf() the indices, elements and decisions.
 rethink the whole thing:
if arr[0] <= arr[n  1], there cannot be a pivot
otherwise, for your array, there must always hold
arr[low] > arr[high]
and for your pivot element
arr[pivot1] > arr[pivot] (be careful to try this right)
Take care of n <= 2 (or think about how the above could take
care of it).
Cheers
Michael

EMail: Mine is an /at/ gmx /dot/ de address.
Rajesh wrote: Question :An element in a sorted list can be found in O(log n) time via binary search. But suppose I rotate the sorted list at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated list in O(log n) time.
Are all elements unique? If there is no restriction on repetitions,
consider the list {2 2 ... 2 3 1 2 2 ... 2}. Can the pivot be found in
O(log n)?
Answer those questions first, then propose a technique.

Thad
Ya all the numbers are unique. Can you suggest ways to correct this
logic?
Thanks,
Rajesh
"Rajesh" <ra***********@gmail.com> writes: Ya all the numbers are unique. Can you suggest ways to correct this logic?
What??
<http://cfaj.freeshell.org/google/>

Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Rajesh wrote: Ya all the numbers are unique. Can you suggest ways to correct this logic?
The logic doesn't need correction, it needs to be determined. So far
you have refused to show your own effort at solving the problem. A good
place to start is try it with pencil and paper, thinking about which
items to compare.

Thad
Rajesh wrote: Question :An element in a sorted list can be found in O(log n) time via binary search. But suppose I rotate the sorted list at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated list in O(log n) time.
Once the position of the pivot element(least element)is known things will be easy. I'm not able to correct the following piece of code(which finds the pivot element's position) to make it work properly. Please suggest ways in which i can do it.
int findPivot(int arr[], int n)
Split the array into an upper half and a lower half.
If neither half is disordered,
then the pivot is the base of the upper half.
Otherwise the pivot is located in the disordered half,
which is where the pivot search should continue.
/* BEGIN new.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int comparison(const void *arg1, const void *arg2);
void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
int main(void)
{
char array[] = "7890123456";
char copy[sizeof array];
char *pivot;
printf("char array[10] = \"%s\";\n\n", array);
strcpy(copy, array);
printf("Value %s\n", copy);
qsort(copy, sizeof copy  1, sizeof *copy, comparison);
printf("Index %s\n", copy);
pivot = findPivot
(array, sizeof array  1, sizeof *array, comparison);
printf("\nThe pivot is array[%d] and is '%c'\n",
(int)(pivot  array), *pivot);
return 0;
}
int comparison(const void *arg1, const void *arg2)
{
return *(char *)arg1  *(char *)arg2;
}
void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;
array = base;
while (compar(array, array + size * (nmemb  1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half  1)) > 0) {
nmemb = half;
} else {
if (compar(
array + size * half,
array + size * (nmemb  1)) > 0)
{
array += half * size;
nmemb = half;
} else {
array += size * half;
break;
}
}
}
return (void *)array;
}
/* END new.c */

pete
pete wrote: Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via binary search. But suppose I rotate the sorted list at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated list in O(log n) time.
Once the position of the pivot element(least element)is known things will be easy. I'm not able to correct the following piece of code(which finds the pivot element's position) to make it work properly. Please suggest ways in which i can do it.
int findPivot(int arr[], int n) Split the array into an upper half and a lower half. If neither half is disordered, then the pivot is the base of the upper half.
Why not the base of the lower half?
Otherwise the pivot is located in the disordered half, which is where the pivot search should continue.
/* BEGIN new.c */
#include <stdio.h> #include <string.h> #include <stdlib.h>
int comparison(const void *arg1, const void *arg2); void *findPivot(const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
int main(void) { char array[] = "7890123456"; char copy[sizeof array]; char *pivot;
printf("char array[10] = \"%s\";\n\n", array); strcpy(copy, array); printf("Value %s\n", copy); qsort(copy, sizeof copy  1, sizeof *copy, comparison); printf("Index %s\n", copy); pivot = findPivot (array, sizeof array  1, sizeof *array, comparison); printf("\nThe pivot is array[%d] and is '%c'\n", (int)(pivot  array), *pivot); return 0; }
int comparison(const void *arg1, const void *arg2) { return *(char *)arg1  *(char *)arg2; }
void *findPivot(const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t half; const unsigned char *array;
array = base; while (compar(array, array + size * (nmemb  1)) > 0) { half = nmemb / 2; if (compar(array, array + size * (half  1)) > 0) { nmemb = half; } else { if (compar( array + size * half, array + size * (nmemb  1)) > 0) { array += half * size; nmemb = half; } else { array += size * half; break; } } } return (void *)array; }
/* END new.c */
Since Rajesh didn't receive the benefit of working out something
himself, I offer him (and others) the following problems for bonus points!
1. Assuming CHAR_MAX < INT_MAX, which line(s) in findPivot will not be
executed for any possible initial char values in array?
2. Given the above code and initialized array, what perverted compare()
function (with no side effects) will cause findPivot to either loop
indefinitely or generate an invalid pointer?

Thad
Thad Smith wrote: pete wrote: Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via binary search. But suppose I rotate the sorted list at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated list in O(log n) time.
Once the position of the pivot element(least element)is known things will be easy. I'm not able to correct the following piece of code(which finds the pivot element's position) to make it work properly. Please suggest ways in which i can do it.
int findPivot(int arr[], int n) Split the array into an upper half and a lower half. If neither half is disordered, then the pivot is the base of the upper half.
Why not the base of the lower half?
Otherwise the pivot is located in the disordered half, which is where the pivot search should continue.
/* BEGIN new.c */
#include <stdio.h> #include <string.h> #include <stdlib.h>
int comparison(const void *arg1, const void *arg2); void *findPivot(const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
int main(void) { char array[] = "7890123456"; char copy[sizeof array]; char *pivot;
printf("char array[10] = \"%s\";\n\n", array); strcpy(copy, array); printf("Value %s\n", copy); qsort(copy, sizeof copy  1, sizeof *copy, comparison); printf("Index %s\n", copy); pivot = findPivot (array, sizeof array  1, sizeof *array, comparison); printf("\nThe pivot is array[%d] and is '%c'\n", (int)(pivot  array), *pivot); return 0; }
int comparison(const void *arg1, const void *arg2) { return *(char *)arg1  *(char *)arg2; }
void *findPivot(const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t half; const unsigned char *array;
array = base; while (compar(array, array + size * (nmemb  1)) > 0) { half = nmemb / 2; if (compar(array, array + size * (half  1)) > 0) { nmemb = half; } else { if (compar( array + size * half, array + size * (nmemb  1)) > 0) { array += half * size; nmemb = half; } else { array += size * half; break; } } } return (void *)array; }
/* END new.c */
Since Rajesh didn't receive the benefit of working out something himself, I offer him (and others) the following problems for bonus points!
1. Assuming CHAR_MAX < INT_MAX, which line(s) in findPivot will not be executed for any possible initial char values in array?
I rewrote findPivot.
void *findpivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;
array = base;
while (compar(array, array + size * (nmemb  1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half  1)) > 0) {
nmemb = half;
} else {
array += size * half;
nmemb = half;
}
}
return (void *)array;
}
2. Given the above code and initialized array, what perverted compare() function (with no side effects) will cause findPivot to either loop indefinitely or generate an invalid pointer?

pete This discussion thread is closed Replies have been disabled for this discussion. Similar topics
57 posts
views
Thread by Egor Bolonev 
last post: by

6 posts
views
Thread by rzed 
last post: by

10 posts
views
Thread by Der Andere 
last post: by

3 posts
views
Thread by Andrew Clark 
last post: by

6 posts
views
Thread by charsh 
last post: by

1 post
views
Thread by J L 
last post: by

1 post
views
Thread by rajesh_krec 
last post: by

4 posts
views
Thread by shrishjain 
last post: by

2 posts
views
Thread by Tilo Pätzold 
last post: by
          