time thereforeit runs in linear time (nlecture- binary search for sorted arraysbinary search is more efficient than linear search the process starts from the middle of the input arrayif the target equals the element in the middlereturn its index if the target is larger than the element in the middlesearch the right half if the target is smallersearch the left half in the following binarysearch(methodthe two index variables first and last indicates the searching boundary at each round int binarysearch(int arr[]int target int first last arr length while (first <last int mid (first last if (target =arr[mid] return mid if (target arr[mid] first mid else last mid return - arr{ target first last mid arr[mid] -go left first last mid arr[mid] -go right first last mid arr[mid] -found target first last mid arr[mid] -go right first last mid arr[mid] -go left first last mid arr[mid] -go right first last -not found