** DATA STRUCTURE**

**UNIT: - ****7 **

__Searching,
Sorting and Complexity__*: -*

Searching

Sequential Search

Binary Search

Sorting

Selection sort

Bubble sort

Quick sort

Merge sort

*Searching: -*

1. **Searching **algorithms are designed to check for an element or
retrieve an element from any data structure where it is stored.

2. **Searching **is the process of finding some particular element
from the list.

3. The search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not.

4. In this algorithm if the element is found in the list then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

5. Two popular searching methods that are widely used are: -

a. Sequential search

b. Binary search

*Sequential Search: -*

1. Sequential search is the simplest searching algorithm and also known as linear search.

2. This searching can be applied for both list of item sorted or unsorted.

3. The **key **which
is to be searched is compared with each element of the list one by one.

4. If key is matched with the element then the search is terminated.

5. If the key is not matched with any element from the list then search is failed.

**Time Complexity: -**

1. The **worst
case** performance of this algorithm is roughly proportional to **n **and represented as **O(n)**.

2. The **best
case **performance in which the first comparison returns a match it requires
a single comparison and hence it is **O(1)**.

3. The **average
case **time depends on the probability that the key will found in the list.
The average and worst case is proportional to **n **hence it is **O(n)**.

**Algorithm for sequential search: -**

**Linear_search
(Array A, value Y)**

Step 1: - for i = 1 to n; (n= number of element in array A)

Step 2: - if A[i] = Y then go to step 4

Step 3: - if i>n then go to step 5

Step 4: - print element found and go to step 6

Step 5: - print element not found

Step 6: - Exit

**Program Logic: -**

**linear_Search**(list, value)

for each item in the list

if match item == value

return the item found

end if

end for

end function **linear_search**

*Binary Search: -*

1. **Binary search** tree technique is very fast and efficient.

2. Binary search algorithm applied only for sorted list of element.

3. In **Binary
search** key is compared with the middle element of the given list, if key
found search got stop.

4. **Binary search** followed divide and conquer approach in which the
give item list is divide into two half after comparing middle element.

5. If key is not found then the key is searched in two halves depending upon the result produced through the match.

**Time Complexity: -**

1. The **worst
case** performance of this algorithm is roughly proportional to **lgn **and represented as **O(log n)**.

2. The **best
case **performance in which the first comparison returns a match it requires
a single comparison and hence it is **O(1)**.

3. The **average
case **time depends on the probability that the key will found in the list.
The average and worst case is proportional to l**lgn **hence it is **O(log n)**.

**Algorithm for sequential search: -**

**Binary_search
(Array A, value Y)**

Step 1: - Initialize i as first index and j as last index;

Step 2: - while i <= j;

Step 3: - (mid= (i+j)/2)

Step 4: - if key == arr[mid] go to step 8

Step 5: - else, compare key with mid is it greater then mid or smaller

Step 6: - if mid < key, j= mid-1, go to step 2

Step 7: - else, mid > key, i=mid + 1 go to step 2

Step 8: - print element found go to step 10

Step 9: - print element not found

Step 10: - exit;

**Program Logic: -**

**binary_Search**(arr,
i, j, key)

while(i<=j)

mid = (i+j)/2;

if (key == arr[mid])

return k; //element found

if (key < arr [mid])

j = k-1;

else

i= k+1;

end while

return -1 //element not found

end function **binary_search**

Next update will available soon..!!

THANK YOU

Regards,

Diploma students

Thank you sir

ReplyDeleteVery helpful notes sir

ReplyDeleteThanks for this notes because it is in easy language.