Author |
Topic: Modified Binary Search (Read 526 times) |
|
mad
Junior Member
Posts: 118
|
 |
Modified Binary Search
« on: Mar 8th, 2008, 6:20am » |
 Quote  Modify
|
An array say A[n] was first sorted and then left or right-shifted any number of times. Search for a given integer k in the array in O(log n) time.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Modified Binary Search
« Reply #1 on: Mar 8th, 2008, 7:12am » |
Quote Modify
|
I assume you mean rotated, rather then shifted; or otherwise you have to tell me what happens with elements that 'drop off'.
You can find the position of the minimum element with an adapted of binary search; then use that as offset to find the kth element from there (modulo the size of the array)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Modified Binary Search
« Reply #2 on: Mar 8th, 2008, 8:00am » |
Quote Modify
|
Code:
#include<stdio.h>
#include<conio.h>
int search(int *arr,int size,int val)
{ int lo=0,hi=size;
int find=0;
while(lo<hi)
{ int mid=(lo+hi)/2;
if(mid==lo)
break;
if(arr[mid]==val)
return mid;
if(arr[lo]<=arr[mid-1])
{ if(val>=arr[lo]&&val<=arr[mid-1])
hi=mid-1;
else
lo=mid+1;
}
else
{ if(val>=arr[mid+1]&&val<=arr[hi])
lo=mid+1;
else
hi=mid-1;
}
}
if(arr[lo]==val)
return lo;
if(arr[hi]==val)
return hi;
return -1;
}
main()
{
int a[9]={6,7,8,9,1,2,3,4,5};
for(int i=0;i<9;i++)
printf("%d\t",a[i]);
printf("\n");
for(i=1;i<=10;i++)
printf("\nIndex of %d is %d",i,search(a,9,i));
getch();
clrscr();
}
|
|
I checked this code and it works for the given input.
Is this also correct?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Modified Binary Search
« Reply #3 on: Mar 8th, 2008, 11:04am » |
Quote Modify
|
To OP: You missed an important requirement. The elements are distinct. Otherwise, worst case the algorithm is O(n).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Modified Binary Search
« Reply #4 on: Mar 8th, 2008, 12:39pm » |
Quote Modify
|
on Mar 8th, 2008, 11:04am, Aryabhatta wrote:| To OP: You missed an important requirement. The elements are distinct. Otherwise, worst case the algorithm is O(n). |
|
Why?
You can split the array into two sorted subarrays in O(log n) in either case; and binary search is O(log n) in either case when you have an sorted array.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Modified Binary Search
« Reply #5 on: Mar 8th, 2008, 2:06pm » |
Quote Modify
|
on Mar 8th, 2008, 12:39pm, towr wrote:
Why?
You can split the array into two sorted subarrays in O(log n) in either case; and binary search is O(log n) in either case when you have an sorted array. |
|
Maybe I am reading the problem wrong... but what if array A contains all ones, except possibly one element, which could be zero. Can we find out in O(log n) time if the array has a zero?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Modified Binary Search
« Reply #6 on: Mar 8th, 2008, 2:19pm » |
Quote Modify
|
on Mar 8th, 2008, 2:06pm, Aryabhatta wrote:| Maybe I am reading the problem wrong... but what if array A contains all ones, except possibly one element, which could be zero. Can we find out in O(log n) time if the array has a zero? |
|
No, you're right; that would be a problem.
But I think that problem is alleviated when less than half the elements have the same value.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print