Scribd
Upload
44 views3 pages

L8 - CD 303 Linear Array - Binary Search

This document discusses binary searching, an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search space in half and focusing on only one subdivision, limiting the number of searches needed to O(log n). The key steps are to start by checking the middle element, eliminate half the array based on whether the target is lower or higher, and repeat on the narrowed range until the element is found. Binary search provides a faster alternative to linear search for large sorted lists but requires the data be pre-sorted and has some implementation challenges.

Uploaded by

Aryaman Bhatnagar
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
44 views3 pages

L8 - CD 303 Linear Array - Binary Search

This document discusses binary searching, an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search space in half and focusing on only one subdivision, limiting the number of searches needed to O(log n). The key steps are to start by checking the middle element, eliminate half the array based on whether the target is lower or higher, and repeat on the narrowed range until the element is found. Binary search provides a faster alternative to linear search for large sorted lists but requires the data be pre-sorted and has some implementation challenges.

Uploaded by

Aryaman Bhatnagar
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/ 3

Topic- Binary Searching

Subject Name/Code- Data Structure/CD 303


Department of CSE-DS

Binary Searching:

• Binary Search is one of the fastest searching algorithms.


• It is used for finding the location of an element in a linear array.
• It works on the principle of divide and conquer technique.
• Binary Search Algorithm can be applied only on Sorted arrays.

The elements must be arranged in:


 Either ascending order if the elements are numbers.
 Or dictionary order if the elements are strings.

To apply binary search on an unsorted array:


 First, sort the array using some sorting technique.
 Then, use binary search algorithm.

Binary Searching (Example):


Element to Search: 75

Algorithm: Binary Searching


Algorithm: BINARY(DATA, LB, UB, ITEM, LOC)
• Here DATA is a sorted array with lower bound LB and upper bound UB, and
ITEM is a given item of information.
• The variables BEG, END and MID denote, respectively, the beginning, end and
middle locations of a segment of elements of DATA. This algorithm finds the
location LOC of ITEM in DATA or sets LOC = NULL.

1. Set BEG:= LB, END:= UB and MID = INT(BEG + END)/2.


2. Repeat Steps 3 and 4 while BEG ≤ END and DATA[MID]≠ ITEM:
3. If ITEM <DATA[MID], then:
Set END:=MID-1.
Else:
Set BEG:= MID + 1.
4. Set MID:= INT(BEG + END)/2.
[End of Step,2 loop.]
5. If DATA[MID] = ITEM, then:
Set LOC:= MID.
Else:
Set LOC: = NULL.
6. Exit.

Time Complexity of Binary Search:


• In each iteration or in each recursive call, the search gets reduced to half of the
array.
• So, for n elements in the array, there are log2n iterations or recursive calls.
Thus, we have:
• Time Complexity of Binary Search Algorithm is O(log2n).
Here, n is the number of elements in the sorted linear array.

Binary Search Algorithm Advantages:


• It eliminates half of the list from further searching by using the result of each
comparison.
• It indicates whether the element being searched is before or after the current
position in the list.
• This information is used to narrow the search.
• For large lists of data, it works significantly better than linear search.

Binary Search Algorithm Disadvantages:


• It employs recursive approach which requires more stack space.
• Programming binary search algorithm is error prone and difficult.
• The interaction of binary search with memory hierarchy i.e. caching is poor.

You might also like