Consider an array

$($

assigned to you below

$)$

$$that has a sequence of negative integers followed by a sequence of positive integers

$($

that could include

$0$

$$as well

$)$

$.$

$$The array is guaranteed to have at least an occurrence of a negative integer and at least an occurrence of a positive integer.

Assume the size of the array is known ahead of time. Also, the array need not be sorted.

$($

a

$)$

$$Design a

$\backslash$

Theta

$($

logn

$)$

$$binary search algorithm to count the number of occurrences of negative integers and positive integers in an array of size

$\text{'}$

n

$\text{'}$

$($

comprising of a sequence of negative integers followed by a sequence of positive integers

$)$

$.$

$$Write the pseudo code of your algorithm as well as clear specify the invariants

$($

properties

$)$

$$of the left index

$($

LI

$)$

$$and the right index

$($

RI

$)$

$$and explain how they are moved in each iteration. Also, explain when does your algorithm terminate and what does it determine by then.

$($

b

$)$

$$Show the execution of your algorithm on the array assigned to you.

Note that you should run only ONE instance of binary search on the array and be able to determine the number of occurrences of negative integers and number of positive integers as well. $\backslash$table$[[\backslash$table$[[$Array$],[$index$]],0,1,2,3,4,5,6,7,8,9,10],[,-23,-55,-74,-25,-61,-23,-27,-18,-70,-38,16]]$