Ceiling in sorted array using binary search

Ceiling in sorted array

In last post, binary search algorithm, we discussed basics of algorithm, it’s implementation and worst case complexity. Today, we will use binary search algorithm to solve another problem called find ceiling in sorted array. To understand problem, first let’s understand what is ceiling? Given an array of integer and element X, ceiling of X is the smallest element in array greater than or equal to X. For example in given array below, ceiling of 7 would be 9. It’s good to know that array is sorted array.

ceiling in sorted array

What will be the most simple solution? To scan through array and see for each index i, if key lies between A[i] and A[i+1] or is equal to A[i], return index i. Worst case complexity would be O(N). But then what’s the fun in solving problem in O(N) complexity!

Ceiling in sorted array : Thought Process

We know that array is sorted, which makes sure that if A[i]> key, all A[j] will also be greater than key for j <i. This helps us to discard some part of array.How?
If all A[j] are greater than key, it means that from i to end of array, minimum element which is greater than key will be A[i] or any element left of i. But surely not on the right side.

This seems like binary search, we split in mid and based on relation of mid with key, we either discard left or right part of array and focus on other. Whenever, you feel like binary search can be used to solve any problem, it’s good to prove that it will work.

Consider all possible solutions as a set S, any value in that set can be answer to problem. Now, let’s say we have a predicate which takes input from candidate set S. This predicate validates that candidate does not violet any condition given problem statement. Predicate function can return any value, for purpose of simplicity, in this article assume that it return true or false.

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x.

Why do I need this abstraction, when I can solve this problem with slight modification of binary search?  That’s true, but then you are not realizing the true power of binary search.  This is because many problems can’t be modeled as searching for a particular value, but it’s possible to define and evaluate a predicate such as “Is there an assignment which costs x or less?”, when we’re looking for some sort of assignment with the lowest cost.

How to find ceiling in sorted array with this method?

What will be our candidate solution set S in this problem? Since, we are looking for an array index which satisfy the condition, that it is smallest element greater than key, every index is in candidate set.
What is the predicate here?  Predicate is : if element at i is greater than key. If it is, predicate returns true else false.

Does the condition to apply binary search apply? If p(x) is true, then for all y>x>, p(y) is also true. So we can apply binary search on candidate set and find which is the least x, where predicate returns true.

Ceiling in sorted array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean predicate(int[] a, int index, int key){
        if(a[index] >= key) return true;

        return false;
    }

    public static int findFirstElementEqualOrGreater(int[] a, int start, 
                          int end, int key){

        while(start < end){
            int mid = start + (end - start) / 2;

            if(predicate(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }

        if(!predicate(a,start, key)) return -1;

        return  start;

    }
    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

        int index = findFirstElementEqualOrGreater(input,0, input.length-1, 15);
        System.out.print(index == -1 ? 
             "Element not found" : "Element found at : " + index);

    }
}

Important part of this implementation is to get lower and higher bounds of solution. In ceiling problem, lowest possible value is 0, first index of array and highest will be array length-1.  How to deal with mid index? Should it be included in any subarray? If yes, which left or right? Answer is it depends what are you looking for. In this example, if A[mid] > key, that is predicate(mid) is true, it is likely to be smallest element which is greater than key, so we must include it in left subarray partition.

high = mid;

However, if predicate(mid) is false, then mid is not required on right subarray.

low = mid+1;

To test that your implementation for any binary search application works, always test your code on a two-element set where the predicate is false for the first element and true for the second.

Complexity of this algorithm to find ceiling in sorted array is O(log N).

Learnings

This problem makes us understand that binary search is not limited to array indices, it can be applied to any discrete set which satisfy mentioned condition. Find, candidate solution set, predicate and make sure that predicate follows that p(x) implies p(y) for all y < x
In next few post, we will take problems from Top coder and SPOJ, and solve them using binary search.

Please feel free to drop us comment or email at communications@algorithmsandme.com if you find anything wrong or missing. If you are willing to write articles and share your knowledge with other learners, please drop us a message.