Array Searching - அடிப்படையில் இருந்து மேம்பட்ட முறைகள் வரை

Searching என்றால் என்ன?

Array searching என்பது:

• ஒரு value array-இல் இருக்கிறதா என்பதை கண்டுபிடிப்பது
• இருந்தால் அது எந்த index-இல் உள்ளது என்பதை அறிதல்

---

உதாரணம்

arr = [10, 20, 30, 40]
target = 30

இந்த உதாரணத்தில்:

• 30 array-இல் உள்ளது
• அது index 2-இல் உள்ளது

---

Linear Search - linear_search (அடிப்படை முறை)

Array sorted ஆக இல்லாத போது, நாம் அடிக்கடி பயன்படுத்தும் முறை Linear Search.

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

செயல்முறை (step-by-step)

• i = 0 → 10 ≠ 30
• i = 1 → 20 ≠ 30
• i = 2 → 30 = target → return 2

நேர சிக்கல் (time complexity)

O(n)

எப்போது பயன்படுத்தலாம்?

• Array unsorted ஆக இருக்கும் போது
• தரவு அளவு குறைவு ஆக இருக்கும் போது

குறைபாடு

• Array பெரியதாக இருந்தால் slow ஆகும்
• தேவையில்லாத comparisons அதிகம்

---

Sorted array logic - sorted_array_logic

Array sorted ஆக இருந்தால், smarter ஆக தேடலாம்.

arr = [10, 20, 30, 40, 50]

Values order-இல் இருப்பதால் நாம் வலது / இடது அரைகளைத் தேர்ந்தெடுக்க முடியும்.

---

Middle index - middle_index_logic

mid = left + (right - left) // 2

---

Binary Search - sorted_array_logic + middle_index_logic

Binary Search (முக்கியமான algorithm)

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid

        elif target < arr[mid]:
            right = mid - 1

        else:
            left = mid + 1

    return -1

உதாரணம்

arr = [10, 20, 30, 40, 50]
target = 40

Step-by-step:

• left = 0, right = 4
• mid = 2 → value = 30
• 30 < 40 → வலது பக்கம்
• left = 3
• mid = 3 → value = 40 → கிடைத்தது

முக்கிய புரிதல்

• Binary search ஒவ்வொரு முறையும் search space-ஐ பாதியாக குறைக்கும்
• அதனால் மிக வேகமானது

நேர சிக்கல்

O(log n)

முக்கிய நிபந்தனை

Binary search வேலை செய்ய array sorted ஆக இருக்க வேண்டும்

---

Rotated sorted array - rotated_array_search

Array முதலில் sorted ஆக இருந்து, பிறகு ஒரு pivot-இல் rotate செய்யப்பட்டிருக்கலாம்.

உதாரணம்:

nums = [4, 5, 6, 7, 0, 1, 2]

முழு array globally sorted இல்லை, ஆனால் left முதல் right வரை எப்போதும் ஒரு பக்கம் sorted ஆக இருக்கும். target எந்த sorted பகுதியில் வரும் என்று binary search O(log n)-இல் தேர்வு செய்யலாம்.

யோசனை

ஒவ்வொரு mid-இலும்:

1. nums[mid] == target → கிடைத்தது
2. nums[left] <= nums[mid] → இடது பகுதி sorted: target அந்த range-இல் இருந்தால் இடது, இல்லையெனில் வலது
3. இல்லையெனில் வலது பகுதி sorted: target அந்த range-இல் இருந்தால் வலது, இல்லையெனில் இடது

Code (தனித்தனி values)

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

உதாரணம்

nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0))  # 4

Duplicate values

பல சமமான values இருந்தால் “எந்த பகுதி sorted?” என்பது ambiguous ஆகலாம்; பல கேள்விகள் தனித்தனி elements என்று கொள்கின்றன.

---

பொதுவான பிழைகள் (binary search)

• Unsorted array-இல் binary search பயன்படுத்துவது
• left / right update தவறு
• Loop condition பிழை

---

Hashing (fast lookup)

பல முறை search செய்ய வேண்டிய போது hashing பயன்படுத்தலாம்.

arr = [10, 20, 30]

lookup = {}
for i in range(len(arr)):
    lookup[arr[i]] = i

print(lookup[30])

நேர சிக்கல்

O(1) (average lookup, map build செய்த பின்)

எப்போது பயன்படுத்தலாம்?

• Repeated search இருக்கும் போது
• Fast lookup தேவை
• Extra memory பயன்படுத்தலாம்

---

Set பயன்படுத்துதல்

ஒரு value இருக்கிறதா என்பது மட்டும் தெரியும் போது:

arr = [10, 20, 30]

s = set(arr)

print(30 in s)

பயன்பாடு

Existence check மட்டும் - index தேவையில்லை போது

---

Two Pointers (sorted_array)

arr = [1, 2, 3, 4, 5]
target = 6

left = 0
right = len(arr) - 1

while left < right:
    pair_sum = arr[left] + arr[right]

    if pair_sum == target:
        print("Found")
        break
    elif pair_sum < target:
        left += 1
    else:
        right -= 1

எப்போது பயன்படுத்தலாம்?

• Pair sum போன்ற பிரச்சினைகள்
• Sorted arrays

(விரிவான பாடத்திற்கு இரண்டாவது குறிப்புகள் பாடத்தைப் பார்க்கவும்)

---

ஒப்பீட்டு அட்டவணை

முறை	நிபந்தனை	நேரம்	Memory
Linear Search	எந்த arrayக்கும்	O(n)	O(1)
Binary Search	sorted array	O(log n)	O(1)
Rotated binary	rotated sorted (தனித்தனி values)	O(log n)	O(1)
Hashing	extra memory	O(1) avg*	O(n)
Set	existence மட்டும்	O(1) avg*	O(n)
Two Pointers	sorted array	O(n)	O(1)

*Map/set build செலவு மற்றும் average-case lookups.

---

முக்கிய புரிதல்

சரியான searching method தேர்ந்தெடுப்பது முக்கியம்.

கேள்விகள்:

• Array sorted ஆக உள்ளதா?
• எத்தனை முறை search செய்ய வேண்டும்?
• Memory பயன்படுத்த முடியுமா?

---

பயிற்சி

• Linear search எழுதுங்கள்
• Binary search trace செய்யுங்கள்
• Rotated sorted array-இல் O(log n) search
• Set பயன்படுத்தி value check செய்யுங்கள்
• Pair sum problem தீருங்கள்

---

இறுதி கருத்து

Searching ஒரு அடிப்படை skill.

ஆனால்:

• சரியான approach தேர்ந்தெடுத்தால் performance மிக உயரும்

Continue here:

/resources/arrays/two-pointers