The binary search algorithm that follows may be used to search an array when the
ID: 3807567 • Letter: T
Question
The binary search algorithm that follows may be used to search an array
when the elements are in order. This algorithm is analogous to the following
approach for finding a name in a telephone book.
a. Open the book in the middle, and look at the middle name on the page.
b. If the middle name isn’t the one you’re looking for, decide whether it
comes before or after the name you want.
c. Take the appropriate half of the section of the book you were looking in
and repeat these steps until you land on the name.
ALGORITHM FOR BINARY SEARCH
1. Let bottom be the subscript of the initial array element.
2. Let top be the subscript of the last array element.
3. Let found be false.
4. Repeat as long as bottom isn’t greater than top and the target has not been found
5. Let middle be the subscript of the element halfway between bottom and
top.
6. if the element at middle is the target
7. Set found to true and index to middle.
else if the element at middle is larger than the target
8. Let top be middle 1.
else
9. Let bottom be middle + 1.
Write and test a function binary_srch that implements this algorithm for an
array of integers. When there is a large number of array elements, which function
do you think is faster: binary_srch or the linear search function of Fig. 7.14 ?
Please write Code in C and provide comments for each action.
Explanation / Answer
Hi, Please find my implementation.
#include <stdio.h>
// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binary_srch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was not present
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = 5;
int x = 10;
int result = binary_srch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array ")
: printf("Element is present at index %d ", result);
return 0;
}
linear Search takes : O(N) time
whereas binary search takes: O(logN) time.
So for larger N, binary search is faster than linear search
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.