Do you really understand binary search ?

Your seniors from Programming Club made a lot of effort in teaching you binary search. They are looking forward to seeing a lot of accepted solutions to this problem. They might even treat everyone who solves this one.

You are given a set of parallel lines having slope -1 on the 2D coordinate. None of the parallel lines are overlapping. All the lines have a positive integral y-intercept (y-intercept is the y coordinate of the point where x co-ordinate is 0).

It is assumed that the point does not lie on any of the lines.

Example:

Input:  arr[] = { 5, 3 }, x = 3, y = 1
Output: 1

Approach

Java

import java.util.Arrays;

public class BinarySearch2 {

    public static void main(String[] args) throws Exception {
        int arr[] = { 5, 3 };
        Arrays.sort(arr);
        int x = 3;
        int y = 1;
        int intercept = x + y;
        int floor = binarySearch(arr, intercept, arr.length);
        System.out.println(floor + 1);
    }

    static int binarySearch(int arr[], int intercept, int n) {
        int lb = 0;
        int ub = arr.length - 1;
        while (lb <= ub) {
            int mid = lb + (ub - lb) / 2;
            if (arr[mid] == intercept) {
                return mid;
            } else if ((arr[mid] < intercept) && 
     (mid == n - 1 || arr[mid + 1] > intercept)) {
                return mid;
            } else if ((arr[mid] > intercept) && 
      (mid == 0 || arr[mid - 1] < intercept)) {
                return mid - 1;
            } else if (arr[mid] > intercept) {
                ub = mid - 1;
            } else {
                lb = mid + 1;
            }
        }
        return -1;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int> arr, int intercept, int n)
{
    int lb = 0;
    int ub = arr.size() - 1;
    while (lb <= ub)
    {
        int mid = lb + (ub - lb) / 2;
        if (arr[mid] == intercept)
        {
            return mid;
        }
        else if ((arr[mid] < intercept) && (mid == n - 1 || 
                 arr[mid + 1] > intercept))
        {
            return mid;
        }
        else if ((arr[mid] > intercept) && (mid == 0 || 
                 arr[mid - 1] < intercept))
        {
            return mid - 1;
        }
        else if (arr[mid] > intercept)
        {
            ub = mid - 1;
        }
        else
        {
            lb = mid + 1;
        }
    }
    return -1;
}

int main()
{
    vector<int> arr = {5, 3};

    sort(arr.begin(), arr.end());
    int x = 3;
    int y = 1;
    int intercept = x + y;
    int floor = binarySearch(arr, intercept, arr.size());
    cout << floor + 1 << "\n";

    return 0;
}