473,856 Members | 1,745 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Rotated Sorted list

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 = n-1, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(arr[low] < arr[mid])
low = mid + 1;
else if (arr[mid] < arr[high])
high = mid-1;
else
return mid;
}
return -1;
}

Please suggest me ways in which i can modify this to work for finding
the pivot element.

Regards,
Rajesh

Feb 1 '06 #1
8 2110
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 = n-1, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(arr[low] < arr[mid])
low = mid + 1;
else if (arr[mid] < arr[high])
high = mid-1;
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[pivot-1] > 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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Feb 1 '06 #2
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
Feb 3 '06 #3
Ya all the numbers are unique. Can you suggest ways to correct this
logic?

Thanks,
Rajesh

Feb 3 '06 #4
"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_Keit h) 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.
Feb 3 '06 #5
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
Feb 3 '06 #6
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(cons t void *arg1, const void *arg2);
void *findPivot(cons t 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(cons t void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(cons t 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
Feb 3 '06 #7
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(cons t void *arg1, const void *arg2);
void *findPivot(cons t 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(cons t void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(cons t 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
Feb 4 '06 #8
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(cons t void *arg1, const void *arg2);
void *findPivot(cons t 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(cons t void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(cons t 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(cons t 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
Feb 4 '06 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

57
3639
by: Egor Bolonev | last post by:
why functions created with lambda forms cannot contain statements? how to get unnamed function with statements?
6
8516
by: rzed | last post by:
I'm using PIL to generate some images which may be rotated at the user's option. When they are rotated, the original image is cropped in the new image (which is fine), and the corners are black (which is not, in this case). I can't find any documented way to change the default fill color (if that's what it is) for the corners, and PIL also doesn't seem to support a flood fill. I have created a flood fill in Python, which works but which...
10
15150
by: Der Andere | last post by:
I need to implement a sorted (ordered) list. STL has no sorted list type as far as I know. Is there a (straight) way to implement a sorted list using STL? BTW: The type of items in the list will be a class. Is it necessary to implement the > or < operators or to write a compare-function that returns the larger or smaller of two classes? Ideally, the list begins with the smallest element. Cheers, Matthias
3
22082
by: Andrew Clark | last post by:
*** post for FREE via your newsreader at post.newsfeed.com *** it's been a while since i have poseted to this newsgroup, but for a long time i was not programming at all. but now that i am out of college and facing the prospect of getting a real job, i need to get back into the game. anyway, i don't know if some of you know the stanford CS library. i took the problem set a while back and have recently rediscovered it adn have been trying...
6
61787
by: charsh | last post by:
Hi, I using the code below to draw a text in a pictureBox1. //Start--------------------------------------------------------------- private void button1_Click(object sender, System.EventArgs e) { Graphics g; g = pictureBox1.CreateGraphics(); g.FillRectangle(Brushes.White,0,0,160,160);
1
1656
by: J L | last post by:
I want to create a sorted list whose values are themselves sorted lists. I wrote the following simple test program but it does not behave as I would expect. What I wanted to do was have the doorConflictList be keyed on a door ID and contain a sorted list called conFlictList. I wrote this expecting the following doorConflictList should end up with 3 items. Item 1 would be a sorted list with 1 item
1
2776
by: rajesh_krec | last post by:
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
4
1867
by: shrishjain | last post by:
Hi All, I need a type where I can store my items in sorted order. And I want to keep adding items to it, and want it to remain sorted. Is there any type in .net which I can make use of. I see there is SortedList<key, value> for hash tables, but could find anything for a sorted list. Currently I am using List<string> and whenever I add an item, I need to
2
5797
by: Tilo Pätzold | last post by:
Hi Everybody (especially Microsoft), we build EMF files with rotated text for export to office (powerpoint, word). It is planned that the text can be edited in the office document. Without the rotate transformation the text stays as a block and can be edited in the office document after ungrouping. But a rotated text leads to single charackters when ungrouping. The following sample code creates an emf file. The file can be dragged to...
0
9908
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9760
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
10777
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10379
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9530
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5759
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4573
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4172
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3198
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.