Question

Describe an algorithm based on the binary search for determining the correct position in which to insert a new element in an already sorted list

Short answer

Not given

Step-by-step solution

Step 1

Let A→sorted array

n→ size of array

x→value to be searched

Final answer                                                                                                                        

The algorithm based on binary search is,

Procedure binary search(x: integer,a_1,a_2,…a_n: increasing integers)

i:=1( iis the left end point of search interval)

j:=n(j is the right end point of search interval)

while i<j

m:=$\left[\left(i+j\right)/2\right]$

if x> a_mthen i:=m+1

else j:=m

if x=a_i then location :=i

else location :=0

return location (location is subscript I of the term a_iequal to x, or 0 if x is not found)