wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Modified Binary Search
        
(Message started by: mad on Mar 8^th, 2008, 6:20am)

Title: Modified Binary Search
Post by mad on Mar 8^th, 2008, 6:20am

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.

Title: Re: Modified Binary Search
Post by towr on Mar 8^th, 2008, 7:12am

I assume you mean rotated, rather then shifted; or otherwise you have to tell me what happens with elements that 'drop off'.

[hide]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)[/hide]

Title: Re: Modified Binary Search
Post by mad on Mar 8^th, 2008, 8:00am

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?

Title: Re: Modified Binary Search
Post by Aryabhatta on Mar 8^th, 2008, 11:04am

To OP: You missed an important requirement. The elements are distinct. Otherwise, worst case the algorithm is O(n).

Title: Re: Modified Binary Search
Post by towr on Mar 8^th, 2008, 12:39pm

on 03/08/08 at 11:04:02, 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.

Title: Re: Modified Binary Search
Post by Aryabhatta on Mar 8^th, 2008, 2:06pm

on 03/08/08 at 12:39:30, 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?

Title: Re: Modified Binary Search
Post by towr on Mar 8^th, 2008, 2:19pm

on 03/08/08 at 14:06:23, 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.