Question is about binary search, help! int binarySearch(int a[], int size, int k

Question

Question is about binary search, help!

int binarySearch(int a[], int size, int k);

Implement a function that uses binary search to find the index position of a given value k in an array of integers whose elements are in strictly increasing order. It searches for a given value k in an array of integers. If the value is found, the function returns the index (or location) of the value in the array; otherwise it returns -1. For example, for v = (-2, 4, 5, 6, 8) and k = 1, the function returns -1; and for k = 6 it returns 3. A declaration of the function is given above. Include test code with assertions

Explanation / Answer

program that finds the index of a given value k using binary search.

int binarySearch (int *Array, int top, int k)

{

Array[]={-2,4,5,6,8};

int lower, middle, upper;

lower = 0;

upper = top;

// loop invariant: if there is actually an i, A[i]=k

// then upper >= i >= lower. Otherwise don't care.

// must find value using middle, otherwise eventually upper < lower and quit.

while ( upper >= lower )

{

middle = ( upper + lower ) / 2;

if (Array[middle] == k)

return( middle );

if (Array[middle] < k)

lower = middle + 1;

else

upper = middle - 1;

};

// never found.

return( -1 );

}

output:

This program is going to check whether the given number is present in the array.If it is present then that index will be returned.otherwise '-1' is displayed.

For example if k==1

for the input A[]=[-2,4,5,6,8}

it searches for 1 in A[],as it is not present it will return -1.

for example if we are searching for 6 it returns 3 as its index is 3

index of -2=0

index of 4=1

index of 5=2

index of 6=3

index of 8=4

so, in this way a program runs

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.