CTCI Challange, DAY 13

Day 13:-

Problam Statement:-Binary Search: Ice Cream Parlor


I didn't solve on paper as i practiced Binary Search algo on system before attemptng this problem.
Solution:-

import java.util.*;

class IceCream implements Comparable {
    int flavorCost;
    int index;

    public IceCream(int flavor, int index) {
        this.flavorCost = flavor;
        this.index = index;
    }

    @Override
    public int compareTo(Object o) {
        IceCream iceCream = (IceCream) o;
        return this.flavorCost - iceCream.flavorCost;
    }

    @Override
    public boolean equals(Object o) {
        IceCream iceCream = (IceCream) o;
        if (this.flavorCost == iceCream.flavorCost && this.index == iceCream.index) {
            return true;
        }
        return false;
    }

}

public class Solution1 {

    public static int binarySearch(int first, int last, IceCream[] arr, int search) {
        if (first > last) {
            return -1;
        }
        int mid = (first + last) / 2;
        if (arr[mid].flavorCost == search) {
            return arr[mid].index;
        }
        if (search > arr[mid].flavorCost) {
            return binarySearch(mid + 1, last, arr, search);
        }
        if (search < arr[mid].flavorCost) {
            return binarySearch(first, mid - 1, arr, search);
        }
        return -1;
    }

    public static void main(String[] args) {

        int t;
        int n, m;

        Scanner in = new Scanner(System.in);
        t = in.nextInt();
        for (int test = 0; test < t; test++) {

            m = in.nextInt();
            n = in.nextInt();
            IceCream[] arr = new IceCream[n];


            for (int i = 0; i < n; i++)
                arr[i] = new IceCream(in.nextInt(), i + 1);
            Arrays.sort(arr);
            int firstIndex = 100000, secondIndex = 100000;
            for (int i = 0; i < n - 1; i++) {
                int search = m - arr[i].flavorCost;
                if (search >= arr[i].flavorCost) {
                    int index = binarySearch(i + 1, n - 1, arr, search);
                    if (index != -1) {
                        System.out.println(Math.min(arr[i].index, index) + " " + Math.max(arr[i].index, index));
                        break;
                    }
                }
            }
        }
    }
}