import java.util.Scanner;
 
/**
* a program which searches an array of integers using a binary search
* method and asks you to type in the number you're looking for, 
* then it will tell you if that number is in the array or not in the array.
*
*
* @author Luca Quacquarelli
* @version v100, March, 18, 2021
**/
 
 
class Main 
{

		 public static void main(String[] args) {
		 
		  //number list
		  int [] list = new int[] 
							{	1,  2,  6,  7, 11,
								12, 16, 19, 29,30,
								34, 36, 37, 39,40,
								46, 56, 66, 67,70,
								72, 73, 74, 85,102 };
		 
		  
			int target;
			Scanner keybd = new Scanner(System.in);
		 
			System.out.println("Binary Search (e.g. 1 or -999 to quit)");
		 
			System.out.println("");
		   
			//while loop is equal to true instead of 1 == 1
			while (true) {
			System.out.print("Enter the number you're looking for > ");
			target = keybd.nextInt();
		 
			if (target == -999) break;//- 999 to stop the program
		 
			   // not equal to -1 we did because of the Boolean 
			if ( binarySearch(list, list.length, target) != -1 ) {
		 
			   System.out.println("Yup, " + target + " found in array list.");
		 
			}// end if
		 
			else {
		 
			   System.out.println("Nope, can't find " + target + " in array list.");
		 
			}// end else
		 
			System.out.println("");
		 
		   }// end while
		 
		 System.out.println("Done.\n");
		 }// end main
		 





		/**
		   The binary search method below cuts the list array in half for every time it goes through the while loop and if it does not find the integer it's looking for it will return -1 which means that the number is not located in the array.
		*
		* @author Luca Quacquarelli
		* @version v100, March, 18, 2021
		**/
		 public static int binarySearch(int [] list, int n, int target) {
		   // left and right int makes the numbers array decrease in size
		   int left = 0;
		   int right = list.length - 1;
		 
		  while (left <= right) {
		 
			// calculate the middle
			int middle = (left + right) / 2;
		 
			//this checks if the target is less than the number we are looking for in the middle
			if (target < list[middle]) { // too high
					  right = middle - 1;
		 
			}// end if
		 
			 //this checks if the target is greater than the number we are looking for in the middle
			else if (target > list[middle]) { // too low
		 
					left = middle + 1;
		 
			}// end else if
		 
			 //this checks if we found the exact target we are looking for in the middle
			else { // just right
		 
					 return middle;
		 
			}// end else
		 
		  }// end while loop
		 
			   return - 1;//this signifies if our Target is not located in the array
		 }//end binarySearch
		 
 



        

        
        /**
           The binary search method below cuts the list array in half for every time it goes through the while loop and if it does not find the integer it's looking for it will return -1 which means that the number is not located in the array.
        *
        * @author Luca Quacquarelli
        * @version v100, March, 18, 2021
        **/
         public static int binarySearch(String [] list, int n, String target) {
           // left and right int makes the numbers array decrease in size
           int left = 0;
           int right = n - 1;
         
          while (left <= right) {
         
            // calculate the middle
            int middle = (left + right) / 2;
         
            //this checks if the target is less than the number we are looking for in the middle
            if (target.compareTo( list[middle] ) < 0) { // too high
                      right = middle - 1;
         
            }// end if
         
             //this checks if the target is greater than the number we are looking for in the middle
            else if (target.compareTo( list[middle]) > 0) { // too low
         
                    left = middle + 1;
         
            }// end else if
         
             //this checks if we found the exact target we are looking for in the middle
            else { // just right
         
                     return middle;
         
            }// end else
         
          }// end while loop
         
               return -1;//this signifies if our Target is not located in the array
         }//end binarySearch
         
    
         
    


}// end class Main