binary search

[samarth123]

Well from the below code i wanted to find the index of the first number higher/equal to x.'x' can be any value.

// binary search implementation.
int binarySearch (int arr[], int num, int size) {
int low, high, mid;
low = 0;
high = size ‐ 1;
while (low <= high) {
/* Calculate mid index */
mid = (low + high) / 2;
/* If element is found at mid index then return the index */
if (arr[mid] == num ) {
return mid+1;
} else if ( arr[mid] > num) {
high = mid ‐ 1;
} else if ( arr[mid] < num) {
low = mid + 1;
}
}
return ‐1;
}

My code gives me the index of the number which is equal to 'x'.
But i have to find the index of the first number which is greater/equal to 'x'.
What modification i have to make for my above code.

[samarth123]

Please reply to my problem ASAP.

[booradley60]

What do you mean find the index of the first number higher/equal to x? If the array looked like this:
{ 10, 7, 20, 8, 9, 1, 3, 16 } what would the output be if x = 3?

If the answer is 10 (first element in the array bigger than x), then your binary search code isn't much good. You just go through the array until you find a number >= 3.

If the answer is 16 (first element in the array bigger than x, starting at x), then you use your binary search function to find the index of 3. Then, write a for loop that goes from that index to the last index in the array.

If the answer is 7 (element that's greater than/equal to x with smallest difference from x), then you need to sort the array. Find 3 (use binary search if you want) then take the element right after it.

What happens if x = 20? (the largest element in the array...)