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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ขั้นตอน 2) กำหนดค่าเริ่มต้น i=0 และ index=-1

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

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

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

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

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

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

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

ชื่อเล่น Code สำหรับอัลกอริธึมการค้นหาแบบลำดับ

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

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 a negative index is not valid
    return -1

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

นี่คือข้อมูลทั้งหมด 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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code ตัวอย่างการค้นหาเชิงเส้น

ตรรกะเดียวกันใน 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)

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

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

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

คำถามที่พบบ่อย