Question

Complete the following function (detailed instructions are given below the code):

private static int predecessor(int array[], int arrayLen, int key) {
// Complete this function.
}

Given a set of numbers, the predecessor of a number x is the highest number in the set that is less than or equal to x. Thus, if I have the set {6; 9; 10; 13; 22; 31; 34; 88}, then the predecessor of 31 is 31 itself, whereas the predecessor of 30 is 22, and the predecessor of 5 is not defined. The predecessor problem has remarkable applications in network routing, where we send information from one computer to another, making email and other uses of the internet possible.
Another application is nearest-neighbor search, akin to locating restaurants on Google Maps, where it returns the closest match to a cuisine of your choice.
Our task is to find predecessor of a number in an array using a Binary Search approach. To this end, complete the following function:
- int ndPredecessor(int A[ ], int arrayLen, int key): returns a position in the array A where the predecessor of key lies. Needless to say that the array A is sorted in ascending order. If the predecessor of key is not defined, return -1.

Caution: You MUST use a binary search approach. Thus, the complexity should be O(log n). If your code ends up scanning the entire array (has a complexity O(n)), your work won't be counted.

Answer 1

// Program for predecessor

public class Main
{

    private static int predecessor (int array[], int arrayLen, int key)
    {
        // To check if the solution exists or not
        if (key<array[0])
        {
            return -1;
        }
        // To check wheather the value is greater than all the values
        else if (key>array[arrayLen-1]){
            return arrayLen-1;
        }

        else{
            // Binary search approach
            int first_value=0;
            int last_value=arrayLen;
            int middle = (first_value + last_value) / 2;
            while (first_value <= last_value)
            {
                if (array[middle] < key)
                {
                    first_value = middle + 1;
                }
                else if (array[middle] == key)
                {
                    return middle;
                }
                else
                {
                    last_value = middle - 1;
                }
                middle = (first_value + last_value) / 2;
            }


                return last_value;
        }
    }
    public static void main (String[]args)

    {
        int[] intArray = new int[]{ 6,9,10,13,22,31,34,88 };
        System.out.println("Predecessor for 5 exist at : "+predecessor(intArray,8,5));
        System.out.println("Predecessor for 31 exist at : "+predecessor(intArray,8,31));
        System.out.println("Predecessor for 30 exist at : "+predecessor(intArray,8,30));
    }
}

// Output of the program

Predecessor for 5 exist at : -1
Predecessor for 31 exist at : 5
Predecessor for 30 exist at : 4

Process finished with exit code 0

// Image for code

// Continued Program

// Output screeshot