โปรแกรมเรียกซ้ำค้นหาแบบเส้นตรงในอาร์เรย์ด้วย C++

ตัวอย่าง

อินพุต − Arr[] = {11, 43, 24, 50, 93, 26, 78}, val = 26

เอาต์พุต − 26 found at index 5

คำอธิบาย −

อิลิเมนต์ในอาร์เรย์เริ่มจากดัชนี 0 ถึง ความยาว-1
ดัชนีแรก=0 ดัชนีสุดท้าย=6: 11 != 26, 78 != 26 → 0+1, 6-1
ดัชนีแรก=1 ดัชนีสุดท้าย=5: 43 != 26, 26 = 26 คืนค่า 5
26 อยู่ที่ดัชนี 5

อินพุต − Arr[] = {11, 43, 24, 50, 93, 26, 78}, val = 66

เอาต์พุต − 66 is not present

คำอธิบาย −

ดัชนีแรก=0 ดัชนีสุดท้าย=6: 11 != 66, 78 != 66 → 1, 5
ดัชนีแรก=1 ดัชนีสุดท้าย=5: 66 != 26, 66 != 26 → 2, 4
ดัชนีแรก=2 ดัชนีสุดท้าย=4: 24 != 66, 93 != 66 → 3, 3
ดัชนีแรก=3 ดัชนีสุดท้าย=3: 50 != 26, 50 != 26 → 4, 2
ดัชนีแรก=3 ดัชนีสุดท้าย=2: 3 > 2 จบการค้นหา 66 ไม่พบ

แนวทางการแก้ปัญหา

ค้นหาแบบเส้นตรงจากทั้งสองข้างของอาร์เรย์ เปรียบเทียบค่าที่ต้องการกับอิลิเมนต์ทั้งสองข้าง หากพบคืนดัชนี มิฉะนั้นเรียกซ้ำด้วยดัชนีแรก+1 และดัชนีสุดท้าย-1 หากดัชนีแรก > ดัชนีสุดท้าย แสดงว่าไม่พบ

• รับอาร์เรย์ Ar[] และค่าที่ต้องการค้นหา val
• ฟังก์ชัน searchRec(int arr[], int start, int end, int num) คืนดัชนีหากพบ
• ตัวแปร result = -99
• หาก arr[start] == num ตั้ง result = start
• หาก arr[end] == num ตั้ง result = end
• หาก start > end ตั้ง result = -1
• หาก result != -99 คืน result มิฉะนั้น เรียก searchRec(arr, start+1, end-1, num)
• ใน main ตรวจสอบค่าที่คืนมาและพิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

int searchRec(int arr[], int start, int end, int num){ 
    int result = -99; 
    if (start > end){ 
        result = -1; 
    } 
    if (arr[start] == num){ 
        result = start; 
    } 
    if (arr[end] == num){ 
        result = end; 
    } 
    if (result != -99){ 
        return result; 
    } 
    return searchRec(arr, start + 1, end - 1, num); 
} 

int main(){ 
    int Arr[] = {11, 43, 22, 56, 33, 26, 78}; 
    int len = sizeof(Arr) / sizeof(Arr[0]); 
    int val = 56; 
    int pos = searchRec(Arr, 0, len - 1, val); 
    if (pos == -1){ 
        cout << val << " is not present"; 
    } else { 
        cout << val << " found at index " << pos; 
    } 
    return 0; 
}

ผลลัพธ์

56 found at index 3