การค้นหาเชิงเส้น: Python, C++ ตัวอย่าง

อัลกอริทึมการค้นหาคืออะไร

อัลกอริธึมการค้นหาได้รับการออกแบบมาเพื่อค้นหาองค์ประกอบหรือวัตถุจากคอลเล็กชั่นขององค์ประกอบหรือวัตถุที่มีโครงสร้างข้อมูลที่กำหนด ตัวอย่างเช่น ค้นหาความสูงขั้นต่ำจากรายการความสูงที่กำหนด หรือค้นหาคะแนนสูงสุดจากรายการหรืออาร์เรย์ของตัวเลข อัลกอริธึมการค้นหายอดนิยมบางส่วนได้แก่ “การค้นหาเชิงเส้น” “การค้นหาแบบไบนารี” “การค้นหาแบบกระโดด” “การค้นหาแบบฟีโบนัชชี” เป็นต้น

การค้นหาเชิงเส้นคืออะไร?

การค้นหาเชิงเส้นเป็นหนึ่งในอัลกอริทึมการค้นหาที่ง่ายที่สุด โดยจะค้นหาองค์ประกอบที่กำหนดทีละองค์ประกอบจากรายการหรืออาร์เรย์ที่กำหนด การค้นหาเชิงเส้นจะทำซ้ำในรายการทั้งหมดและตรวจสอบว่าองค์ประกอบใดองค์ประกอบหนึ่งเท่ากับองค์ประกอบการค้นหาหรือไม่ เรียกอีกอย่างว่า ค้นหาตามลำดับ

ฟังก์ชั่นการค้นหาเชิงเส้นทำหน้าที่อะไร?

อาร์เรย์ของจำนวนเต็มจะได้รับเป็น “Numbers” และตัวแปร “รายการ” มีเลขจำนวนเต็มที่ต้องการค้นหา

ขณะนี้อัลกอริทึมการค้นหาเชิงเส้นสามารถให้ผลลัพธ์ต่อไปนี้:

• “-1”; ซึ่งหมายความว่าไม่พบองค์ประกอบที่กำหนดในอาร์เรย์
• ตัวเลขใดๆ ระหว่าง 0 ถึง n-1; หมายความว่าพบองค์ประกอบการค้นหา และส่งคืนดัชนีขององค์ประกอบบนอาร์เรย์ ในที่นี้ “n” แสดงถึงขนาดของอาร์เรย์

การค้นหาเชิงเส้นทำงานอย่างไร

สมมติว่ามีอาร์เรย์ที่มีตัวเลขจำนวนเต็ม หน้าที่ของอาร์เรย์คือค้นหาตัวเลขที่กำหนดในอาร์เรย์

• หากตัวเลขอยู่ในอาร์เรย์ เราจำเป็นต้องส่งคืนดัชนีของตัวเลขนั้น
• หากไม่พบหมายเลขที่ระบุ ก็จะส่งกลับ -1

ในผังงาน “ข้อมูล” คืออาร์เรย์จำนวนเต็ม “N” คือขนาดของอาร์เรย์ และ “รายการ” คือตัวเลขที่เราต้องการค้นหาในอาร์เรย์

ผังงานสำหรับอัลกอริทึมการค้นหาเชิงเส้น:

นี่คือขั้นตอนของผังงาน:

ขั้นตอน 1) อ่านรายการค้นหา “รายการ”

ขั้นตอน 2) เริ่มต้น i=0 และดัชนี=-1

ขั้นตอน 3) ถ้าฉัน

ขั้นตอน 4) หาก Data[i] เท่ากับ “รายการ” ให้ไปที่ขั้นตอนที่ 5 หรือไปที่ขั้นตอนที่ 6

ขั้นตอน 5) Index = i (เนื่องจากรายการพบได้ที่ดัชนี no i) ไปที่ขั้นตอนที่ 8

ขั้นตอน 6) ฉัน = ฉัน +1

ขั้นตอน 7) ไปที่ขั้นตอนที่ 3

ขั้นตอน 8) หยุด

เพื่อความง่าย เราจะยกตัวอย่างอาร์เรย์ของจำนวนเต็ม การค้นหาเชิงเส้นยังใช้ได้กับสตริง อาร์เรย์ของอ็อบเจ็กต์ หรือโครงสร้างอีกด้วย

รหัสหลอกสำหรับอัลกอริธึมการค้นหาตามลำดับ

function linearSearch: in →Data[], item
foundAt = -1
for i in (0 to data.length): if data[i] equals item
// item is found in the array
// returning the index
return i
// item not found in the array
// -1 means no item found, as negative index is not valid
return -1

C++ ตัวอย่างโค้ดการค้นหาเชิงเส้น

#include < bits / stdc++.h >
    using namespace std;
int linearSearch(int * arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}
int main() {
    int array[] = {
        1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
    };
    int n = sizeof(array) / sizeof(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Output:

Enter a number to search: -10
-10 is found at index 14

Python ตัวอย่างโค้ดการค้นหาเชิงเส้น

def linearSearch(data, item):
    for i in range(len(data)):
    if data[i] == item:
    return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else :
    print("{} was not found".format(item))

Output:

Enter a number to search: -10
-10 is found at index 14

การวิเคราะห์ความซับซ้อนของอัลกอริทึมการค้นหาเชิงเส้น

โดยทั่วไป ความซับซ้อนของเวลาหมายถึงจำนวนเวลาของ CPU ในการทำงานบางอย่าง ในอัลกอริทึมการค้นหาเชิงเส้น งานคือการค้นหาคีย์การค้นหาจากองค์ประกอบของอาร์เรย์

ความซับซ้อนของเวลามี 3 ประเภท ได้แก่:

• สถานการณ์กรณีที่เลวร้ายที่สุด
• สถานการณ์จำลองกรณีที่ดีที่สุด
• สถานการณ์กรณีเฉลี่ย

ความซับซ้อนของเวลาในการค้นหาเชิงเส้นในสถานการณ์ที่เลวร้ายที่สุด:

สมมติว่าเราจำเป็นต้องทำการค้นหาเชิงเส้นในอาร์เรย์ที่มีขนาด "n" เราสามารถค้นหารายการค้นหาระหว่างดัชนี 0 ถึง n-1 สถานการณ์กรณีที่เลวร้ายที่สุด อัลกอริทึมจะพยายามจับคู่องค์ประกอบทั้งหมดจากอาร์เรย์กับองค์ประกอบการค้นหา

ในกรณีนั้น ความซับซ้อนในกรณีเลวร้ายที่สุดจะเป็น O(n) โดยที่สัญลักษณ์ O ขนาดใหญ่ หมายถึงฟังก์ชันความซับซ้อน

ความซับซ้อนของเวลาในการค้นหาเชิงเส้นในสถานการณ์ที่ดีที่สุด:

สมมติว่าเรากำลังค้นหาองค์ประกอบที่อยู่ในตำแหน่งแรกในอาร์เรย์ ในสถานการณ์นี้ อัลกอริทึมการค้นหาเชิงเส้นจะไม่ค้นหาองค์ประกอบทั้งหมด n รายการในอาร์เรย์ ดังนั้นความซับซ้อนจะอยู่ที่ O(1) ซึ่งหมายความว่าเวลาจะคงที่

ความซับซ้อนของเวลาในการค้นหาเชิงเส้นในกรณีเฉลี่ย:

เมื่อพบองค์ประกอบที่ดัชนีกลางของอาร์เรย์ เราสามารถกล่าวได้ว่าความซับซ้อนของเคสโดยเฉลี่ยในการค้นหาเชิงเส้นคือ O(N) โดยที่ N หมายถึงความยาวของอาร์เรย์

ความซับซ้อนของพื้นที่ของอัลกอริทึมการค้นหาเชิงเส้น

ความซับซ้อนของพื้นที่สำหรับการค้นหาเชิงเส้นจะเป็น O(N) เสมอ เนื่องจากเราไม่จำเป็นต้องจัดเก็บหรือใช้ตัวแปรชั่วคราวใดๆ ในฟังก์ชันการค้นหาเชิงเส้น

วิธีปรับปรุงอัลกอริธึมการค้นหาเชิงเส้น

การค้นหาสามารถทำได้หลายครั้งตลอดวงจรชีวิตของโปรแกรม นอกจากนี้ยังเป็นไปได้ที่เรากำลังเรียกใช้อัลกอริทึมการค้นหาเชิงเส้นและค้นหาคีย์เฉพาะใดๆ หลายครั้ง เราสามารถใช้ “อัลกอริธึมการค้นหาแบบไบนารี” ถ้าอาร์เรย์เป็นอาร์เรย์ที่เรียงลำดับ

สมมติว่าอาร์เรย์ประกอบด้วยตัวเลข 10 ตัว และพบองค์ประกอบเป้าหมายที่ดัชนีที่ 5000 ดังนั้นอัลกอริทึมจะพยายามเปรียบเทียบ 5000 องค์ประกอบ ขณะนี้ การเปรียบเทียบเป็นงานที่ต้องใช้ CPU มาก หากต้องการปรับให้อัลกอริทึมการค้นหาเชิงเส้นเหมาะสมที่สุด เรามีตัวเลือกสองทาง

• การขนย้าย
• ย้ายไปด้านหน้า

ขนย้าย:

ในวิธีนี้ เราจะสลับองค์ประกอบการค้นหากับองค์ประกอบก่อนหน้าในอาร์เรย์ ตัวอย่างเช่น สมมติว่าคุณมีอาร์เรย์ดังต่อไปนี้:

ข้อมูล[] = {1,5,9,8,7,3,4,11}

ตอนนี้ เราต้องการค้นหา 4. ขั้นตอนการขนย้าย:

ขั้นตอน 1) พบ “4” ที่ดัชนี 6 ใช้เวลาเปรียบเทียบหกครั้ง

ขั้นตอน 2) สลับข้อมูล[6] และข้อมูล[5] จากนั้นอาร์เรย์ข้อมูลจะมีลักษณะดังนี้:

ข้อมูล[] = {1,5,9,8,7,4,3,11}

ขั้นตอน 3) ค้นหา 4 อีกครั้ง พบที่ดัชนี 5 คราวนี้ใช้เวลาเปรียบเทียบห้าครั้ง

ขั้นตอน 4) สลับข้อมูล [5] และข้อมูล [4] จากนั้นอาร์เรย์ข้อมูลจะมีลักษณะดังนี้:

ข้อมูล [] = {1,5,9,8,4,7,3,11}

ตอนนี้ หากคุณสังเกตเห็นว่า ยิ่งมีการค้นหาคีย์บ่อยขึ้นเท่าใด ดัชนีก็จะยิ่งลดน้อยลงเท่านั้น ทำให้จำนวนการเปรียบเทียบลดลง

ย้ายไปด้านหน้า:

ในวิธีนี้ เราจะสลับองค์ประกอบการค้นหาในดัชนีที่ 0 เพราะหากค้นหาอีกครั้งเราจะพบได้ในเวลา O(1)

การประยุกต์ใช้อัลกอริธึมการค้นหาเชิงเส้น

ต่อไปนี้คือแอปพลิเคชันการค้นหาเชิงเส้นบางส่วนที่เราสามารถใช้ได้

• สำหรับอาร์เรย์ขนาดเล็กหรือเพียงไม่กี่องค์ประกอบในรายการ การใช้การค้นหาเชิงเส้นจะง่ายกว่า
• วิธีค้นหาเชิงเส้นสามารถใช้ได้ทั้งแบบเดี่ยวหรือแบบ อาร์เรย์หลายมิติ หรือโครงสร้างข้อมูลอื่นๆ
• โดยทั่วไป การค้นหาเชิงเส้นจะง่ายและมีประสิทธิภาพในการค้นหาข้อมูล "แบบไม่เรียงลำดับ" เราสามารถดึงข้อมูลเดียวจากรายการที่ไม่เรียงลำดับที่กำหนดได้อย่างง่ายดาย