Scribd
Upload
116 views12 pages

Searching & Sorting in Arrays

The document discusses two searching algorithms - linear search and binary search. Linear search compares the target item to each element in the array sequentially. Binary search works on a sorted array by repeatedly dividing the search space in half and focusing on one sub-region. It also briefly covers bubble sort for sorting an array.

Uploaded by

Ankit Rajput
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
116 views12 pages

Searching & Sorting in Arrays

The document discusses two searching algorithms - linear search and binary search. Linear search compares the target item to each element in the array sequentially. Binary search works on a sorted array by repeatedly dividing the search space in half and focusing on one sub-region. It also briefly covers bubble sort for sorting an array.

Uploaded by

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

Data Structures

Lecture 7: Searching in Array

By
Ravi Kant Sahu
Asst. Professor,
Lovely Professional University, Punjab
Contents
• Sorting (Bubble Sort)
• Searching (Linear Search and Binary Search)
• Review Questions

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Searching
1. Linear Search:
• Compares the item of interest with each element
of Array one by one.
• Traverses the Array sequentially to locate the
desired item.

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Linear Search Algorithm
• LINEAR_SEARCH (DATA, N, ITEM, LOC)

1. [Insert ITEM at the end of DATA] Set Data [N+1]= ITEM.


2. [Initialize Counter] Set LOC=1.
3. [Search for ITEM.]
Repeat while DATA [LOC] != ITEM
Set LOC = LOC +1.
[End of loop.]
4. [Successful?] if LOC = N + 1, then Set LOC = 0.
5. Exit.

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Work Space
•

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


2. Binary Search
• BINARY ( DATA, LB, UB, ITEM, LOC )
1. [Initialize Segment Variables]
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.
[End of if Structure.]
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.
[End of if structure.]
6. Exit. Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India
Limitations of Binary Search
• Although the complexity of Binary Search is
O (log n), it has some limitations:
1. the list must be sorted
2. one must have direct access to the middle
element in any sublist.

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Work Space
•

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Sorting (Bubble Sort)
• Sorting refers to the operation of rearranging the elements
of A so they are in some particular order.

• Complexity of Bubble Sort Algorithm is: O(n2)

• Example of Bubble Sort

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Bubble Sort Algorithm
Bubble (DATA, N)
1. Repeat Step 2 and 3 for K=1 to N-1.
2. [Initialize Pass Pointer P] Set P=1.
3. [Execute Pass] Repeat while P <= N-K.
(a) if DATA [P] > DATA [P+1], then:
Interchange DATA [P] and DATA[P+1]
[End of if Structure.]
(b) Set P = P+1.
[End of Inner Loop.]
[End of Step1 Outer Loop.]
4. Exit

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Work Space
•

Ravi Kant Sahu, Asst. Professor @ LPU Phagwara (Punjab) India


Questions

You might also like