15. Basic Searching

একটি ডাটা কালেকশন (যেমন: অ্যারে বা লিস্ট) থেকে নির্দিষ্ট কোনো ভ্যালু খুঁজে বের করার পদ্ধতিকেই সার্চিং বলে। ডাটা স্ট্রাকচারে সার্চিং অত্যন্ত কমন এবং গুরুত্বপূর্ণ একটি কাজ।

---

1. লিনিয়ার সার্চ (Linear Search)

এটি সার্চিংয়ের সবচেয়ে সহজ পদ্ধতি। এতে অ্যারের শুরু থেকে শেষ পর্যন্ত প্রতিটি এলিমেন্ট এক এক করে চেক করা হয়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. অ্যারের প্রথম ইনডেক্স থেকে দেখা শুরু করুন।
2. বর্তমান এলিমেন্টটি কী আমরা যা খুঁজছি (target) তার সমান?

• যদি হ্যাঁ হয়, তবে ইনডেক্সটি রিটার্ন করুন।
• যদি না হয়, তবে পরের ইনডেক্সে যান।

3. অ্যারের শেষ পর্যন্ত যদি টার্গেট খুঁজে না পাওয়া যায়, তবে -১ রিটার্ন করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Best Case: O(1) - যদি প্রথম এলিমেন্টেই টার্গেট পাওয়া যায়।
• Worst Case: O(n) - যদি টার্গেটটি একদম শেষে থাকে বা অ্যারেতে না থাকে।
• Average Case: O(n) - গড়ে n/2 বার খুঁজতে হয়।
• Space Complexity: O(1) - অতিরিক্ত কোনো মেমরি প্রয়োজন হয় না।

Java Implementation

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1; // Not found
}

Python Implementation

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1 # Not found

---

2. বাইনারি সার্চ (Binary Search)

যদি ডাটা সর্টেড থাকে, তবে বাইনারি সার্চ সবচেয়ে কার্যকর। এটি প্রতি স্টেপে সার্চ এরিয়াকে অর্ধেক করে ফেলে।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. দুটি পয়েন্টার নিন: low (শুরুতে) এবং high (শেষে)।
2. মাঝখানের ইনডেক্স mid বের করুন: mid = low + (high - low) / 2।
3. যদি arr[mid] টার্গেটের সমান হয়, তবে mid রিটার্ন করুন।
4. যদি arr[mid] টার্গেটের চেয়ে ছোট হয়, তবে বাম দিকের অংশ বাদ দিন (low = mid + 1)।
5. যদি arr[mid] টার্গেটের চেয়ে বড় হয়, তবে ডান দিকের অংশ বাদ দিন (high = mid - 1)।
6. low <= high হওয়া পর্যন্ত লুপটি চালান।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Best Case: O(1) - যদি প্রথমবার mid বের করার সময়ই টার্গেট পাওয়া যায়।
• Worst Case: O(log n) - প্রতিবার সার্চ এরিয়া অর্ধেক হয়ে যায়।
• Average Case: O(log n)
• Space Complexity: O(1) - ইটারেটিভ মেথডে অতিরিক্ত মেমরি লাগে না।

Java Implementation (Iterative)

public int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Python Implementation (Iterative)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

---

3. কমপ্লেক্সিটি তুলনা (Quick Summary)

Algorithm	Best Case	Worst Case	Average Case	Space
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)

---

4. রোটেটেড সর্টেড অ্যারে (Search in Rotated Array)

🛠 কর্মপদ্ধতি (Logic Detail)

সরাসরি বাইনারি সার্চ না চালিয়ে চেক করতে হয় কোন অংশটি সর্টেড অবস্থায় আছে (বামে নাকি ডানে)। তারপর সেই অনুযায়ী টার্গেট কোন রেঞ্জে আছে তা ডিসাইড করে পুনরায় বাইনারি সার্চের লজিক অ্যাপ্লাই করা হয়।

Java Implementation

public int searchRotated(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;

        if (nums[low] <= nums[mid]) { // Left part is sorted
            if (target >= nums[low] && target < nums[mid]) high = mid - 1;
            else low = mid + 1;
        } else { // Right part is sorted
            if (target > nums[mid] && target <= nums[high]) low = mid + 1;
            else high = mid - 1;
        }
    }
    return -1;
}

Python Implementation

def search_rotated(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target: return mid

        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]: high = mid - 1
            else: low = mid + 1
        else:
            if nums[mid] < target <= nums[high]: low = mid + 1
            else: high = mid - 1
    return -1

---

IMPORTANT

বড় ডাটা সেটের ক্ষেত্রে লিনিয়ার সার্চ এড়িয়ে চলাই ভালো, কারণ এর টাইম কমপ্লেক্সিটি অনেক বেশি।

---

TIP

কোডিং ইন্টারভিউতে যদি ডাটা সর্টেড থাকে, তবে সব সময় বাইনারি সার্চ অ্যাপ্লাই করে টাইম কমপ্লেক্সিটি কমানোর চেষ্টা করুন।