Floor and floor X from sorted array

Question

Find the gender and ceil of the number X from an array that is already sorted. eg.

a [] = {3, 7, 9, 10, 15}

• if X = 2, floor = N / A, ceil = 3
• if X = 3, floor = 3, ceil = 3
• if X = 4, floor = 3, ceil = 7
• if X = 16, floor = 15, ceil = N / A

I think most of us are aware of the solution, that is, we can find the floor / ceil by a modified binary search. But the problem with the modified binary search is that we need to take care of a lot of boundary conditions. But I found that the same binary search algorithm works, but for gender we just need to write if low > high return low and for ceil if low > high return high . And if floor return -1 shows N / A, and if ceil returns a value that is larger than the array index than show N / A.

algo for the floor:

 int floorSearch(int a[], int low, int high, int x) { if(low > high){ return low; } int mid = (low+high)/2; if(a[mid]>x){ return floorSearch(a, low, mid-1, x); } else if(a[mid]<x){ return floorSearch(a, mid+1, high, x); } else{ return mid; } } 

and for ceil:

 int ceilSearch(int a[], int low, int high, int x) { if(low > high){ return high; } int mid = (low+high)/2; if(a[mid]>x){ return ceilSearch(a, low, mid-1, x); } else if(a[mid]<x){ return ceilSearch(a, mid+1, high, x); } else{ return mid; } } 

It is very simple, right? I checked a lot of inputs and it works, but I could not prove the correctness of the algorithm. Can someone give him an attempt to prove the correctness, or you can also give a sample input for which this algo will fail. Thanks.

Answer 1

Advice:

• This may be too obvious, but evidence of the correctness of these algorithms will follow the recursive structure of the algorithm; those. using evidence of structural induction.

• Look at the proof of the standard binary search and find out how it is built.

Answer 2

There is a traditional error in the code. It uses int mid = (low+high)/2; . If the array is very large, it is possible to add to the overflow to a negative result, which makes the average negative.

The error can be fixed using int mid = (low+high)>>>1; as done in java.util.Arrays binarySearch methods. >>> 1 makes, in fact, an unsigned division into 2.

Answer 3

Since you only changed the condition if(low > high) , pay attention to what is equivalent to a normal binary search. Understanding the proof of binary search, determining the correctness here should be almost trivial.

Answer 4

Here is a test case that will break your code for ceilSearch.

a = {3, 7, 9, 11, 13}, x = 10.

I list low, high, and medium in each recursive call:

(0, 4, 2) → a [2] = 9 <x

(3, 4, 3) → a [3] = 11> x

(3, 2, 2) → low> high, low low = 2.

The correct answer will be 3, not 2.