L$1$: Search algorithm implementation and analysis

Experimental goal: Implement linear search and binary search algorithms

Experimental steps

$1.$ Linear search implementation:

$-$ Implement a method linearSearch$($int$[]$ arr, int target$)$ to check each element in the array in turn, return the index if the target is found, otherwise return $-1.$

$2.$ Binary search implementation:

$-$ Implement a method binarySearch$($int$[]$ arr, int target$)$ to find the target element in a sorted array. Use recursion or iteration to gradually divide the array into two halves until the target is found or the division cannot be continued.

Sample code: The following is the sample code for linear search and binary search:

$```$

for $($int i $=0$; i $$ arr.length; i$++)\{$

if $($arr$[$i$]==$ target$)\{$

return i;

$\}$

$\}$

return $-1$;

$\}$

$//$ Binary Search $($Iterative$)$

public static int binarySearch$($int$[]$ arr, int target$)\{$

int left $=0,$ right $=$ arr.length $-1$;

while $($left right$)\{$

int mid $=$ left $+($right $-$ left$)/2$;

if $($arr$[$mid$]==$ target$)\{$

return mid;

$\}$

if $($arr$[$mid$]$ target$)\{$

left $=$ mid $+1$;

$\}$ else $\{$

right $=$ mid $-1$;

$\}$

$\}$

return $-1$;

$\}$

$```$

$//$ Linear Search

public static int linearSearch$($int$[]$ arr, int target$)\backslash \{1)$ What is the time complexity of the two search algorithms? Why is there a difference in their performance for large arrays?

$2)$ Why does binary search require the array to be in order?

$3)$ Based on experimental data, how do linear search and binary search perform when searching for a non$-$existent target?