Scribd
Upload
19 views1 page

3 - Binary Search

The document outlines a program design for an online shopping website, 'Digishop', to track product availability using a recursive binary search algorithm in C. It describes the binary search process, including the algorithm steps and how to measure the time taken for searches with varying numbers of elements. The aim is to efficiently determine if a product is in stock based on its ID and visualize the search time against the number of elements.

Uploaded by

deckofcards89
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views1 page

3 - Binary Search

The document outlines a program design for an online shopping website, 'Digishop', to track product availability using a recursive binary search algorithm in C. It describes the binary search process, including the algorithm steps and how to measure the time taken for searches with varying numbers of elements. The aim is to efficiently determine if a product is in stock based on its ID and visualize the search time against the number of elements.

Uploaded by

deckofcards89
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

3.

“Digishop” a online shopping website needs to keep track of the product availability based
on the product ID. Design a program in C to read the product ID provided by the customer
and search for it’s availability by using Binary search method and display the relevant
message whether the product is in stock or not. Determine the time required to search for
the product. Repeat the experiment for different values of n and plot a graph of the time
taken versus n. (n=no of elements).

Aim: To perform recursive binary search and to find the time required to search
elements.

Theory: Binary search is a remarkably efficient algorithm for searching in a sorted array.
it works by comparing a search key k with the array's middle element A[m]. If they
match, the algorithm stops; otherwise, the same operation is repeated recursively for the
first half of the array K<A[m]and for the second half if K>A[m].

ALGORITHM BinarySearch(n)

Step 1: Store the first and last element in different variables


low = 0
high = n-1

Step 2: dividing the list in two equal parts and checking for the key element in mid
position
while(low <= high)
mid=(low+high)/2 //Divide the list into two equal parts
if(item=a[mid[]]
return mid+1 //return the position if search successful

Step 3: checking for the key element in left side of the mid element or right side of
the mid element and storing the position

if(item<a[mid]) //item not found in the list


return binary (a, item, low, mid-1) //search in left side of the array
else
return binary (a , item, mid+1, high) //search in the right side of
the array
end if
end while

Step 4: return negative value if element not found


return -1 //item is not present in the list

You might also like