Question

Consider a binary-search method in an array that reports whether an object is in the array. The documentation indicates that the caller must pass in a sorted array or the results are unspecified. According to strict design-by-contract, who is responsible for checking that the array is sorted

Answer 1

#include<iostream.h>

#include<conio.h>

void sort(int A[], int N)

{int I,J,tmp;

for(I=0;I<N;I++)

{for(J=0;J<N;J++)

{if(A[J]>A[J+1])

{tmp=A[J];A[J]=A[J+1];A[J+1]=tmp;}}}}

void main()

{int a[15],I,n,l,u,sh,mid,k=0;

clrscr();

cout<<”Enter the array size”;

cin>>n;

l=0;u=n-1;

cout<<”\nEnter the array elements”<<endl;

for(i=0;i<n;i++)

cin>>a[i];

sort(a,n);

cout<<”\nEnter search element”;

cin>>sh;

cout<<”\nNow, applying N=Binary Search”<<endl;

while(l<=u)

{mid=(l+u)/2;

If(a[mid]>sh)

u=mid-1;

if(a[mid]<sh)

l=mid+1;

if(a[mid]==sh){k=1;break;}}

if(k==1)

cout<<”\n Element is present at “<<(mid+1)<<endl;

else

cout<<”\n Element not found”;

getch();

}

Explanation:

Binary Search is a type of search method which is more effective and takes more traversals than the linear search. It compares the each element to the middle element. If the element is found, it gives the position otherwise it will give no result.