import java.util.Scanner;

class BinarySearch {
    public static int binarySearch(int[] numArr, int search) {
        int mid;
        int low = 0;
        int high = numArr.length - 1;

        while(high >= low) {
            mid = (high + low) / 2;
            if(numArr[mid] < search) {
                low = mid + 1; // Search top half
            }
            else if(numArr[mid] > search) {
                high = mid - 1; // Search bottom half
            }
            else {
                return mid;
            }
        }
        return -1; // If not found
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] nums = {1,2,3,4,5,6};
        int search;
        int searchIndex;

        // Print out all the contents of the number array
        System.out.println("Numbers in array: ");
        for(int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();

        // Enter number to search
        System.out.println("Enter number to search: ");
        search = sc.nextInt();

        searchIndex = binarySearch(nums, search);
        
        if(searchIndex == -1) {
            System.out.println(search + " was not in the array!");
        }
        else {
            System.out.println(search + " was found at index " + searchIndex);
        }

        sc.close();
    }
}