next higher number in a sorted array
I have a sorted array ( in ascending order) and I want to find the subscript of a number in the array which is the the next highest number to a given number. For example,if I have 67 as a given number and if I have an array x=(23,36,45,62,79,103,109), then how do I get the subscript 5 from x (to get 79 which is the next highest to 67) without using a loop?
do a binary search, and returns the index +1 when the algo stops.
ReplyDeletenormal binary search searches for number equality...please check.
ReplyDeletePseudo code:
ReplyDeletesearch(arr, left, right, val)
{
if(left == right)
return left+1;
mid = (left+right)/2
if(val <= arr[mid])
return search(arr, left, mid-1, val)
return search(arr, mid+1, right, val)
}
a fix:
ReplyDeleteint search(int* arr, int left, int right, int val)
{
if(right < left)
return right+1;
int mid = (left+right)/2;
if(val <= arr[mid])
return search(arr, left, mid-1, val);
return search(arr, mid+1, right, val);
}
is this correct?
please response :)
@Or in your code if you will give 23 as input val then o/p index is 0 ,but according to problem it should be 1.so please check for equality condition rest if working fine...
ReplyDeleteplease see this
ReplyDeleteint search(int* arr, int left, int right, int val)
{
if(right < left)
return -1;
int mid = (left+right)/2;
if(val < arr[mid] && (mid == 0 || val >= arr[mid-1]))
return mid;
if(val >= arr[mid])
return search(arr, mid+1, right, val);
return search(arr, left,mid-1, val);
}
@PRIYARANJAN:
ReplyDeleteif you give 23 as input then you get 0 which is actually good output because it's zero based.
@Or according to problem statement you have to find subscript of next higher number in the array.so on inputting 23 it should give next higher number than 23, and you haven't checked for non-existence of value..please comment..:)
ReplyDeleteOk. now i hope that's fine:
ReplyDeleteint search(int* arr, int left, int right, int val)
{
if(right < left)
return right+1;
int mid = (left+right)/2;
if(val < arr[mid])
return search(arr, left, mid-1, val);
return search(arr, mid+1, right, val);
}