Write a method that searches an Array of integers for a given integer using the

Binary Search Algorithm. If the input integer is found in the array, return

You can assume that the given array of integers is already sorted

in ascending order.

Examples:

Binary Search Algorithm. If the input integer is found in the array, return

`true`

. Otherwise, return `false`

.You can assume that the given array of integers is already sorted

in ascending order.

Examples:

`binarySearch({2,5,7,8,9},9) -> true`

`binarySearch({2,8,9,12},6) -> false`

`binarySearch({2},4) -> false`

`binarySearch({},9) -> false`

` {} -> [Empty] Array `

Need a **hand?** Try out these hints, one at a time.

Check the element at the middle of the array. If that's not your element, repeat the same process by narrowing the search down to either the first half or the second half of the array. Consider the value of the middle element to choose which half to search.

Binary search

uses the 'guess a number' approach.

1. Your guess is that the middle element of the sorted array

is your answer.

Maintain

2. If the middle element is not your answer, search the element in one of the two subarrays.

3. If the middle element is higher than the search target, search it in the first half of the array, i.e. left of the middle element.

4. If the middle element is lower than the search target, search it in the second half of the array, i.e. right of the middle element.

Keep repeating steps 1 to 4 until the element is found or the start and the end indices cross over each other.

uses the 'guess a number' approach.

1. Your guess is that the middle element of the sorted array

is your answer.

Maintain

`start`

, `end`

and `mid `

indices to keep a track of the two subarrays formed by splitting the given array at the middle2. If the middle element is not your answer, search the element in one of the two subarrays.

3. If the middle element is higher than the search target, search it in the first half of the array, i.e. left of the middle element.

4. If the middle element is lower than the search target, search it in the second half of the array, i.e. right of the middle element.

Keep repeating steps 1 to 4 until the element is found or the start and the end indices cross over each other.

public static Boolean binarySearch(int[] arr, int n){ }

**C**

**Java**

**Python**