Tuesday, June 2, 2020

SEARCHING ALGORITHM

1. LINEAR SERACH ALGORITHM - CLICK HERE
2. BINARY SEARCH ALGORITHM - CLICK HERE

BINARY SEARCH ALGORITHM STEP BY STEP

🎯 What is Binary Search?

Binary Search is a fast searching technique used to find an element in a sorted array by repeatedly dividing the search space into half.

📌 Definition

Binary Search is a divide-and-conquer algorithm that finds an element in a sorted list by comparing the target value with the middle element.

⚠️ Important Condition

✔ The array must be sorted (ascending or descending)
❌ Binary search does NOT work on unsorted data

🧠 How Binary Search Works

Steps:

Find middle element
Compare middle element with target
If match → stop
If target is smaller → search left half
If target is larger → search right half
Repeat until found or range becomes empty

📊 Example

Sorted Array:


A = [10, 20, 30, 40, 50, 60, 70]

Target:


Find 50

Step-by-step:

Step	Low	High	Mid	Value	Action
1	0	6	3	40	50 > 40 → right half
2	4	6	5	60	50 < 60 → left half
3	4	4	4	50	✅ Found

💻 Algorithm (Pseudocode)


BinarySearch(A, key)

1. low = 0
2. high = n - 1

3. while low <= high
4.     mid = (low + high) / 2
5.     if A[mid] == key
6.         return mid
7.     else if key < A[mid]
8.         high = mid - 1
9.     else
10.        low = mid + 1

11. return -1

🐍 Python Program for Binary Search


def binary_search(arr, key):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == key:
            return mid
        elif key < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

# Example
arr = [10, 20, 30, 40, 50, 60, 70]
key = 50

result = binary_search(arr, key)

if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

Output:


Element found at index: 4

⚡ Time Complexity

Case	Complexity
Best Case	O(1)
Worst Case	O(log n)
Average Case	O(log n)

📊 Why Binary Search is Fast?

Each step reduces search space by half:

Example:

8 elements → 4 → 2 → 1

So it grows very slowly compared to linear search.

🆚 Binary Search vs Linear Search

Feature	Linear Search	Binary Search
Data Requirement	Unsorted	Sorted
Speed	Slow (O(n))	Fast (O(log n))
Method	Sequential	Divide & Conquer
Efficiency	Low	High

📌 Advantages of Binary Search

Very fast for large datasets
Reduces comparisons drastically
Efficient algorithm

❌ Disadvantages

Requires sorted data
Not suitable for dynamic/unsorted lists
More complex than linear search

🧠 Real Life Example

Finding a word in dictionary 📖
Searching a name in sorted telephone directory 📞

📌 Summary

Binary search works only on sorted data.
It divides the list into halves repeatedly.
It is much faster than linear search.
Time complexity is O(log n).

❓ Important Questions

Short Questions

What is binary search?
What is the condition for binary search?
What is time complexity of binary search?
What is mid element?
Give one real-life example.

Long Questions

Explain binary search with example.
Write algorithm of binary search.
Write Python program for binary search.
Compare linear and binary search.
Explain time complexity of binary search.

LINEAR SEARCH ALGORITHM STEP BY STEP

🎯 What is Linear Search?

Linear Search is a simple searching technique used to find an element in a list or array by checking each element one by one from the beginning to the end.

📌 Definition

Linear Search is a sequential searching algorithm where each element is compared with the target value until a match is found or the list ends.

🧠 How Linear Search Works

Start from the first element
Compare each element with the target value
If match found → Stop
If not found → Move to next element
Continue until end of list

📊 Example

Array:


A = [10, 25, 30, 45, 60]

Target:


Find 30

Step-by-step Process:

Step	Element Checked	Result
1	10	Not match
2	25	Not match
3	30	✅ Match found

💻 Algorithm (Pseudocode)


LinearSearch(A, n, key)

1. for i = 0 to n-1
2.     if A[i] == key
3.         return i
4. return -1

🐍 Linear Search Program (Python)


def linear_search(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

# Example
arr = [10, 25, 30, 45, 60]
key = 30

result = linear_search(arr, key)

if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

Output:


Element found at index: 2

⚡ Best Case, Worst Case

Case	Condition	Complexity
Best Case	Element at first position	O(1)
Worst Case	Element at last or not present	O(n)
Average Case	Random position	O(n)

📌 Advantages of Linear Search

Very simple to understand
Works on unsorted data
No extra memory required

❌ Disadvantages

Slow for large data sets
Not efficient compared to binary search

🆚 Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Data Requirement	Unsorted	Sorted
Speed	Slow	Fast
Method	Sequential	Divide & Conquer

🧠 Real Life Example

Searching a name in attendance register
Finding a contact in phone list (unsorted)

📌 Summary

Linear search checks elements one by one.
It is simple but inefficient for large data.
Best used for small or unsorted datasets.

❓ Important Questions

Short Questions

What is linear search?
What is time complexity of linear search?
Give one advantage of linear search.
Is sorting required in linear search?
Write one real-life example.

Long Questions

Explain linear search with example.
Write algorithm of linear search.
Write a program for linear search.
Compare linear and binary search.
Explain best and worst case of linear search.

GRAPH THEORY

1. GRAPH THEORY ALGORITHMS - CLICK HERE

2. GRAPH THEORY N.DEO CHAPTER WISE QUESTION - CLICK HERE

GRAPH THEORY ALGORITHMS

1. DEPTH FIRST SEARCH - CLICK HERE

2. BREADTH FIRST SEARCH - CLICK HERE

3. FLOYD ALGORITHM -

4. WARSHALL ALGORITHM -

5. PRIM'S ALGORITHM - CLICK HERE

6. KRUSKAL'S ALGORITHM -CLICK HERE

7. DYSTRA'S ALGORITHM - CLICK HERE

BREADTH FIRST SEARCH ( BFS) ALGORITHM IMPLEMENTATION STEP BY STEP