Searching ka matlab hota hai kisi element ko kisi data structure (array, list, etc.) ke andar find karna. C++ mein searching ke multiple techniques hote hain. Yahaan hum sabse popular techniques ko cover karenge.

1. Linear Search

Linear Search mein ham searching linearly karte hai matlab ki array ke har ek element ko one by one check karte hai, agar element aur given value match hoti hai to ham us element ke index ko return kar dete hai. Ye sabse basic aur easy algorithm hoti hai.

How this works ?

Hume ek array/list di gayi hai aur ek target element diya gaya hai. Humein yeh find karna hai ki:

1. Kya target element array mein present hai?
2. Agar hai toh kis index pe hai?

Examples:

1. Array: [10, 20, 30, 40, 50], Target: 30 → Found at index 2
2. Array: [5, 15, 25], Target: 10 → Not found

Approach

Method: Linear Search (Basic)

1. Array ke har element ko ek ek karke check karo
2. Current element aur target ko compare karo
3. Agar match mila toh return karo index
4. Agar pure array traverse kar liya aur nahi mila toh return -1

Dry Run

Array: [10, 20, 30, 40, 50]

Target: 30

1. Index 0: 10 ≠ 30 → continue
2. Index 1: 20 ≠ 30 → continue
3. Index 2: 30 == 30 → match found!
4. Return index 2

Agar Target 60 hota:

1. Sab elements check honge
2. Koi element target se match nahi hoga
3. Return -1

Code

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    // Array ke har element ko check karo
    for(int i = 0; i < n; i++) {
        if(arr[i] == target) {
            return i;  // Element mil gaya
        }
    }
    return -1;  // Element nahi mila
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 30;
    
    int result = linearSearch(arr, n, target);
    
    if(result == -1) {
        cout << "Element not found in array";
    }
    else {
        cout << "Element found at index: " << result;
    }
    
    return 0;
}

Code Explanation:

1. Function Parameters:

• arr[]: Input array
• n: Array ka size
• target: Jis element ko dhundhna hai

1. Loop Through Array:

• Har index i ke liye check karo
• Agar arr[i] target ke equal hai toh , i return karo

1. Element Not Found:

• Pure array traverse karne ke baad bhi nahi mila toh -1 return karo

1. Main Function:

• Array aur target initialize kiya
• Function call kiya
• Result ke hisab se output diya

Time Complexity Analysis

• Best Case: O(1) - Pehle hi element pe mil gaya
• Worst Case: O(n) - Last element pe mila ya nahi mila
• Average Case: O(n) - Beech mein kahi milta hai

Advantages of Linear Search

1. Simple implement karna
2. Sorted/Unsorted dono arrays pe kaam karta hai
3. Kisi bhi data structure pe use kar sakte hain (arrays, linked lists etc.)

2. Binary Search

Binary Search ek efficient searching algorithm hai, but condition ye hai ki array must be sorted. Is algorithm ko implement karne ke liye array ka sorted hona zaruri. Hum is algorithm mein middle element ko check karte hain aur search space ko half karte jaate hain.

Is algorithm main, ek sorted array diya gaya hai aur ek target element diya gaya hai. Hame efficiently yeh find karna hai:

1. Kya target element array mein present hai?
2. Agar hai toh kis index pe hai?

Examples:

1. Array: [10, 20, 30, 40, 50], Target: 30 → Found at index 2
2. Array: [5, 15, 25], Target: 10 → Not found

Approach

Key Concept:

• Binary search tab kaam karta hai jab array sorted ho
• Har step mein search space ko aadha (half) kar dete hain

Steps:

1. Initialize: , low = 0 , high = n-1 
2. Mid Point Calculate Karo: , mid = low + (high-low)/2 
3. Compare Karo:

• Agar arr[mid] == target → return mid
• Agar  arr[mid] < target → right half mein search karo (low = mid+1)
• Agar [arr[mid] > target→ left half mein search karo (high = mid-1)

1. Repeat: Jab tak low <= high
2. Not Found: Agar loop khatam ho gaya toh -1 return karo

Dry Run (Step-by-Step Execution)

Array: [10, 20, 30, 40, 50]

Target: 30

1. Iteration 1:

• low=0, high=4
• mid=2 (30)
• arr[2] == 30 → Found!

Agar Target 35 hota:

1. Iteration 1:

• low=0, high=4
• mid=2 (30)
• 30 < 35 → low=3

1. Iteration 2:

• low=3, high=4
• mid=3 (40)
• 40 > 35 → high=2

1. Loop Break: low > high → Not found

Code with Detailed Explanation

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n-1;
    
    while(low <= high) {
        int mid = low + (high - low)/2;  // Overflow se bachne ka tarika
        
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] < target) {
            low = mid + 1;  // Right half mein search karo
        }
        else {
            high = mid - 1; // Left half mein search karo
        }
    }
    
    return -1;  // Element nahi mila
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 30;
    
    int result = binarySearch(arr, n, target);
    
    if(result == -1) {
        cout << "Element not found in array";
    }
    else {
        cout << "Element found at index: " << result;
    }
    
    return 0;
}

Code Explanation:

1. Initialization: lowand high pointers
2. Loop: Jab tak low <= high
3. Mid Calculation: low + (high-low1)/2(overflow prevention)
4. Comparisons:

• Equal case: return index
• Less than case: right half mein jao
• Greater than case: left half mein jao

1. Not Found: Loop ke baad -1 return

Time Complexity Analysis

• Best Case: O(1) - Middle element hi target hai
• Worst/Average Case: O(log n) - Har step mein search space half ho jata hai

Advantages of Binary Search

1. Linear search se bahut faster (O(log n) vs O(n))
2. Large datasets ke liye perfect

Important Notes

1. Pre-condition: Array sorted hona chahiye
2. Overflow Prevention: mid = low + (high-low)/2se karna better hai