package com.company;

import java.util.*;

public class Main {

    public static void main(String[] args) {
    // write your code here
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(5);
        list.add(7);
        list.add(12);
        list.add(25);
        list.add(30);
        list.add(36);


        Collections.sort(list);
        System.out.println(binarySearch(list, 2, 0));
        System.out.println(list);
    }

    static int binarySearch(List<Integer> list, Integer element, Integer index){
        if (list.isEmpty()){
            return -1;
        }
        int listSizeIndex = list.size();
        int listMiddleIndex = listSizeIndex / 2;
        if (list.get(listMiddleIndex) == element){
            return index + listMiddleIndex;
        }
        else if (list.get(listMiddleIndex) < element){
            List<Integer> newList = new ArrayList<>(list.subList(listMiddleIndex + 1, listSizeIndex));
            return binarySearch(newList, element, index + listMiddleIndex + 1);
        }
        else {
            List<Integer> newList = new ArrayList<>(list.subList(0, listMiddleIndex));
            return binarySearch(newList, element, index);
        }
    }

}