3) Написать программу, реализующую линейный и бинарный поиск заданного значения в массиве целых чисел. Размерность массива и искомое значение вводить с клавиатуры. Массив заполнять случайными числами. Сравнить количество шагов для размерности 10, 1000 и 1000. Оценить сложность каждого из алгоритмов. Реализовать бинарный поиск используя рекурсивн…

Search of elementh in array

//Бинарный поиск работает эффективнее и быстрее, чем линейный, так как множество ненужных чисел попросту отсекается.
//Координаты числа - его индекс в массиве (отсчёт начинается с нуля).
import java.util.*;
public class search {
static Scanner scan=new Scanner(System.in);
	public static void main(String[] args){
		
		int array[];
		System.out.print("Enter size of array: ");
		int n=scan.nextInt();
	    array=new int[n];
	    for (int i=0; i<array.length; i++)
	    	array[i]=(int)(Math.random()*n);
	    
	    System.out.print("Array: ");
	    for(int i:array)
	    	System.out.print(i + " ");
	    
        System.out.print("Enter numeric to search: ");
        int numeric=scan.nextInt();
	    System.out.print("Choose method: line search (1) or binary search (2) ");
	    int method=scan.nextInt();
	    if (method==1) lineSearch(array, numeric);
	    else if (method==2) {
	    int left=0; int right=array.length;
	    binarySearch(array, numeric, left, right);}
	}
	
	 private static void binarySearch(int[]array, int numeric, int left, int right){
    	 sort(array);
 		System.out.print("New array: ");
 		for(int i:array)
 			System.out.print(i+" "); 
    	 binarySearchRecursion(array, numeric, left, right);
     }
	 
     private static void binarySearchRecursion(int[]array, int numeric, int left, int right){	    	
    	 int mid=left+(right-left)/2;		
    	 
    	 if (left>=right){
  			System.out.print("There is no more "+numeric+" in array. ");
  			return; }
    	   			
    	if (array[mid]==numeric) 
				System.out.print("Index of "+ numeric+ " is "+ mid+ ". ");
    			
    	else if (numeric>array[mid])
			binarySearchRecursion(array, numeric, mid+1, right);
		else if (numeric<array[mid])
			binarySearchRecursion(array, numeric, left, mid-1);		
	}		
	
	private static void lineSearch(int[] array, int numeric){
		for (int i=0; i<array.length; i++){
			if (array[i]==numeric){
				System.out.print("Index of "+numeric+" is "+i+". ");
			}
			 else if (i==(array.length-1)){
				 System.out.print("There is no more "+numeric+" in array. ");
			 }
			 }
	}
	static void swap (int[] array, int i, int j) {
        int k = array[i];
        array[i] =array[j];
        array[j] = k;
    }         
    static void sort(int[] array){
        for(int i = array.length-1 ; i >= 0 ; i--){
            for(int j = 0 ; j < i ; j++){
                if( array[j] > array[j+1] )
                   swap(array, j, j+1);
            }
        }
    }
}