ບົດທີ 8 Searching Algorithms

2. ປະເພດຂອງ searching Algorithms

ມີຫຼາຍປະເພດຂອງວິທີການຄົ້ນຫາ, ລວມທັງ:

1. 1. ການຄົ້ນຫາເສັ້ນຊື່: ການຄົ້ນຫາເສັ້ນ, ເຊິ່ງເອີ້ນກັນວ່າການຄົ້ນຫາຕາມລໍາດັບ, ແມ່ນວິທີການຄົ້ນຫາແບບງ່າຍໆທີ່ກວດເບິ່ງແຕ່ລະອົງປະກອບຂອງອາເຣຫຼືລາຍຊື່ຈົນກ່ວາມັນຊອກຫາມູນຄ່າເປົ້າຫມາຍ. ມັນມີຄວາມຊັບຊ້ອນເວລາຂອງ O(n), ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງອົງປະກອບໃນໂຄງສ້າງຂໍ້ມູນ.

   2. ການຄົ້ນຫາຖານສອງ: ການຄົ້ນຫາແບບຖານສອງແມ່ນວິທີການຄົ້ນຫາທີ່ມີປະສິດທິພາບຫຼາຍຂຶ້ນທີ່ເຮັດວຽກໂດຍການແບ່ງເວລາຄົ້ນຫາເປັນເຄິ່ງຫນຶ່ງໃນແຕ່ລະຂັ້ນຕອນ. ມັນຮຽກຮ້ອງໃຫ້ມີການຈັດລຽງໂຄງສ້າງຂໍ້ມູນກ່ອນແລະມີຄວາມຊັບຊ້ອນເວລາຂອງ O(log n), ເຊິ່ງໄວກວ່າການຄົ້ນຫາເສັ້ນຊື່ສໍາລັບ arrays ຫຼືລາຍຊື່ຂະຫນາດໃຫຍ່.

   3. ການຄົ້ນຫາ nterpolation: ການຄົ້ນຫາ interpolation ແມ່ນ variant ຂອງການຄົ້ນຫາຄູ່ທີ່ໃຊ້ສູດ interpolation ເພື່ອຄາດເດົາຕໍາແຫນ່ງຂອງມູນຄ່າເປົ້າຫມາຍໃນໂຄງສ້າງຂໍ້ມູນ. ມັນເຮັດວຽກໄດ້ດີທີ່ສຸດເມື່ອຂໍ້ມູນຖືກແຈກຢາຍຢ່າງສະໝ່ຳສະເໝີ ແລະ ມີຄວາມຊັບຊ້ອນເວລາຂອງ O(log log n) ໃນກໍລະນີສະເລ່ຍ ແລະ O(n) ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ.

   4. ການຄົ້ນຫາແບບ Exponential: ການຄົ້ນຫາແບບ Exponential ແມ່ນວິທີການຄົ້ນຫາທີ່ເຮັດວຽກໂດຍການເພີ່ມຂະຫນາດສອງເທົ່າຂອງໄລຍະການຄົ້ນຫາໃນແຕ່ລະຂັ້ນຕອນຈົນກ່ວາມູນຄ່າເປົ້າຫມາຍຖືກພົບເຫັນຫຼືເກີນ. ມັນຮຽກຮ້ອງໃຫ້ມີໂຄງສ້າງຂໍ້ມູນເພື່ອຈັດຮຽງກ່ອນແລະມີຄວາມຊັບຊ້ອນເວລາຂອງ O(log n).

   5. ການຄົ້ນຫາທີ່ອີງໃສ່ hash: ການຄົ້ນຫາທີ່ອີງໃສ່ hash ໃຊ້ຟັງຊັນ hash ເພື່ອຄິດໄລ່ດັດສະນີເຂົ້າໄປໃນ array ຂອງ buckets ຫຼື slots, ບ່ອນທີ່ມູນຄ່າເປົ້າຫມາຍຄາດວ່າຈະພົບເຫັນ. ປະເພດຂອງວິທີການຄົ້ນຫານີ້ມີຄວາມຊັບຊ້ອນເວລາສະເລ່ຍຂອງ O(1), ເຮັດໃຫ້ມັນໄວຫຼາຍ, ແຕ່ມັນສາມາດຊ້າກວ່າສູດການຄິດໄລ່ອື່ນໆໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ.

ການເລືອກວິທີການຄົ້ນຫາທີ່ຖືກຕ້ອງແມ່ນຂຶ້ນກັບຄຸນລັກສະນະຂອງໂຄງສ້າງຂໍ້ມູນແລະຄວາມຕ້ອງການສະເພາະຂອງການຄົ້ນຫາ. ການຄົ້ນຫາເສັ້ນແມ່ນງ່າຍດາຍແລະງ່າຍທີ່ຈະປະຕິບັດ, ແຕ່ມັນສາມາດຊ້າສໍາລັບ arrays ຫຼືລາຍຊື່ຂະຫນາດໃຫຍ່. ການຄົ້ນຫາແບບຖານສອງແມ່ນມີປະສິດທິພາບຫຼາຍກວ່າເກົ່າສໍາລັບການຈັດລຽງ arrays ຫຼືລາຍຊື່, ແຕ່ມັນຮຽກຮ້ອງໃຫ້ມີການຈັດຮຽງຂໍ້ມູນລ່ວງຫນ້າ. ການຄົ້ນຫາ interpolation ແລະການຄົ້ນຫາ exponential ສາມາດໄວກວ່າການຄົ້ນຫາຄູ່ໃນບາງກໍລະນີ, ແຕ່ພວກເຂົາມີຄວາມຕ້ອງການສະເພາະທີ່ຕ້ອງໄດ້ຮັບການຕອບສະຫນອງ. ການຄົ້ນຫາທີ່ອີງໃສ່ hash ແມ່ນໄວຫຼາຍໂດຍສະເລ່ຍ, ແຕ່ມັນສາມາດມີການປະຕິບັດທີ່ບໍ່ດີໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ.

3. ການຄົ້ນຫາແບບ Linear search

ການຄົ້ນຫາເສັ້ນ, ເຊິ່ງເອີ້ນກັນວ່າການຄົ້ນຫາຕາມລໍາດັບ, ແມ່ນວິທີການຄົ້ນຫາແບບງ່າຍໆທີ່ກວດເບິ່ງແຕ່ລະອົງປະກອບຂອງອາເຣຫຼືລາຍຊື່ຈົນກ່ວາມັນຊອກຫາມູນຄ່າເປົ້າຫມາຍ.

ນີ້ແມ່ນວິທີທີ່ມັນເຮັດວຽກ:

1. ເລີ່ມຕົ້ນໃນຕອນຕົ້ນຂອງ array ຫຼືລາຍຊື່.

2. ປຽບທຽບແຕ່ລະອົງປະກອບທີ່ມີຄ່າເປົ້າຫມາຍ.

3. ຖ້າອົງປະກອບກົງກັນ, ໃຫ້ກັບຄືນດັດຊະນີຂອງມັນ.

4. ຖ້າຈຸດສິ້ນສຸດຂອງ array ຫຼືລາຍຊື່ຖືກບັນລຸໂດຍບໍ່ໄດ້ຊອກຫາມູນຄ່າເປົ້າຫມາຍ, ໃຫ້ກັບຄືນ -1.

ນີ້ແມ່ນຕົວຢ່າງການປະຕິບັດການຄົ້ນຫາເສັ້ນຊື່ໃນ Python:

def linear_search(arr, target):

    for i in range(len(arr)):

        if arr[i] == target:

            return i

    return -1

ຟັງຊັນ linear_search ໃຊ້ເວລາສອງ arguments: arr, ເຊິ່ງເປັນ array ຫຼືລາຍຊື່ເພື່ອຄົ້ນຫາ, ແລະເປົ້າຫມາຍ, ເຊິ່ງເປັນຄ່າທີ່ຈະຄົ້ນຫາ. ມັນໃຊ້ສໍາລັບ loop ເພື່ອເຮັດຊ້ໍາແຕ່ລະອົງປະກອບໃນ array ຫຼືລາຍຊື່. ຖ້າອົງປະກອບກົງກັບຄ່າເປົ້າຫມາຍ, ຟັງຊັນຈະສົ່ງຄືນດັດຊະນີຂອງມັນ. ຖ້າຈຸດສິ້ນສຸດຂອງ array ຫຼືລາຍຊື່ຖືກບັນລຸໂດຍບໍ່ໄດ້ຊອກຫາຄ່າເປົ້າຫມາຍ, ຟັງຊັນຈະກັບຄືນ -1.

ການຄົ້ນຫາເສັ້ນຊື່ມີຄວາມຊັບຊ້ອນເວລາຂອງ O(n), ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງອົງປະກອບໃນໂຄງສ້າງຂໍ້ມູນ. ນີ້ຫມາຍຄວາມວ່າເວລາທີ່ມັນໃຊ້ເວລາເພື່ອດໍາເນີນການຄົ້ນຫາເສັ້ນຊື່ເພີ່ມຂຶ້ນຕາມເສັ້ນກົງກັບຂະຫນາດຂອງວັດສະດຸປ້ອນ. ສໍາລັບ arrays ຫຼືບັນຊີລາຍຊື່ຂະຫນາດໃຫຍ່, ການຄົ້ນຫາເສັ້ນອາດຈະບໍ່ແມ່ນວິທີການຄົ້ນຫາທີ່ມີປະສິດທິພາບທີ່ສຸດທີ່ຈະໃຊ້. ຢ່າງໃດກໍ່ຕາມ, ມັນງ່າຍດາຍແລະງ່າຍຕໍ່ການປະຕິບັດແລະສາມາດເປັນປະໂຫຍດສໍາລັບຊຸດຂໍ້ມູນຂະຫນາດນ້ອຍຫຼືສໍາລັບສະຖານະການທີ່ຂໍ້ມູນບໍ່ໄດ້ຖືກຈັດຮຽງ.

4. ການຄົ້ນຫາຖານສອງ Binary search

ການຄົ້ນຫາຖານສອງແມ່ນວິທີການຄົ້ນຫາທີ່ມີປະສິດທິພາບຫຼາຍຂຶ້ນທີ່ເຮັດວຽກໂດຍການແບ່ງໄລຍະການຄົ້ນຫາເປັນເຄິ່ງຫນຶ່ງໃນແຕ່ລະຂັ້ນຕອນ. ມັນຮຽກຮ້ອງໃຫ້ມີໂຄງສ້າງຂໍ້ມູນເພື່ອຈັດຮຽງກ່ອນ.

ນີ້ແມ່ນວິທີທີ່ມັນເຮັດວຽກ:

1. 1. ຊອກຫາອົງປະກອບກາງຂອງ array.

   2. ປຽບທຽບອົງປະກອບກາງກັບມູນຄ່າເປົ້າຫມາຍ.

   3. ຖ້າອົງປະກອບກາງກົງກັບຄ່າເປົ້າຫມາຍ, ສົ່ງຄືນດັດຊະນີຂອງມັນ.

   4. ຖ້າອົງປະກອບກາງໃຫຍ່ກວ່າມູນຄ່າເປົ້າຫມາຍ, ຄົ້ນຫາເຄິ່ງຊ້າຍຂອງອາເຣ.

   5. ຖ້າອົງປະກອບກາງແມ່ນຫນ້ອຍກວ່າມູນຄ່າເປົ້າຫມາຍ, ຄົ້ນຫາເຄິ່ງຂວາຂອງອາເຣ.

   6. ເຮັດຊ້ໍາຂັ້ນຕອນ 1-5 ຈົນກ່ວາມູນຄ່າເປົ້າຫມາຍຖືກພົບເຫັນຫຼືໄລຍະການຄົ້ນຫາຫວ່າງເປົ່າ.

ນີ້ແມ່ນຕົວຢ່າງການປະຕິບັດການຄົ້ນຫາສອງໃນ Python:

def binary_search(arr, target):

    left = 0

    right = len(arr) - 1

    while left <= right:

        mid = (left + right) // 2

        if arr[mid] == target:

            return mid

        elif arr[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return -1

ຟັງຊັນ binary_search ໃຊ້ເວລາສອງ arguments: arr, ເຊິ່ງເປັນ array ທີ່ຖືກຈັດຮຽງຫຼືລາຍຊື່ເພື່ອຄົ້ນຫາ, ແລະເປົ້າຫມາຍ, ເຊິ່ງເປັນມູນຄ່າທີ່ຈະຄົ້ນຫາ. ມັນໃຊ້ວົງຮອບໃນຂະນະເພື່ອແບ່ງໄລຍະການຄົ້ນຫາຊ້ຳໆໃນເຄິ່ງໜຶ່ງຈົນກວ່າຈະພົບເຫັນຄ່າເປົ້າໝາຍ ຫຼືໄລຍະຫ່າງຫວ່າງເປົ່າ. ຕົວແປຊ້າຍແລະຂວາເປັນຕົວແທນຈຸດສິ້ນສຸດຊ້າຍແລະຂວາຂອງໄລຍະການຄົ້ນຫາ, ຕາມລໍາດັບ. ຕົວແປກາງສະແດງເຖິງດັດຊະນີຂອງອົງປະກອບກາງຂອງໄລຍະການຄົ້ນຫາ. ຖ້າອົງປະກອບກາງກົງກັບຄ່າເປົ້າຫມາຍ, ຟັງຊັນຈະສົ່ງຄືນດັດຊະນີຂອງມັນ. ຖ້າບໍ່ດັ່ງນັ້ນ, ຖ້າອົງປະກອບກາງແມ່ນຫນ້ອຍກວ່າເປົ້າຫມາຍ ມູນຄ່າ, ການຄົ້ນຫາແມ່ນສືບຕໍ່ໃນເຄິ່ງຂວາຂອງໄລຍະການຄົ້ນຫາ. ຖ້າອົງປະກອບກາງແມ່ນໃຫຍ່ກວ່າມູນຄ່າເປົ້າຫມາຍ, ການຄົ້ນຫາແມ່ນສືບຕໍ່ຢູ່ໃນເຄິ່ງຊ້າຍຂອງໄລຍະການຄົ້ນຫາ.

ການຄົ້ນຫາຖານສອງມີຄວາມຊັບຊ້ອນເວລາຂອງ O(log n), ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງອົງປະກອບໃນໂຄງສ້າງຂໍ້ມູນ. ນີ້ຫມາຍຄວາມວ່າເວລາທີ່ມັນໃຊ້ເວລາເພື່ອດໍາເນີນການຄົ້ນຫາຖານສອງຈະເພີ່ມຂຶ້ນຕາມ logarithmically ກັບຂະຫນາດຂອງການປ້ອນຂໍ້ມູນ. ສໍາລັບ arrays ຫຼືບັນຊີລາຍຊື່ຂະຫນາດໃຫຍ່, ການຄົ້ນຫາສອງສາມາດໄວກວ່າການຄົ້ນຫາເສັ້ນຊື່. ຢ່າງໃດກໍ່ຕາມ, ມັນຮຽກຮ້ອງໃຫ້ມີການຈັດຮຽງຂໍ້ມູນກ່ອນ, ເຊິ່ງສາມາດເພີ່ມເວລາການປຸງແຕ່ງເພີ່ມເຕີມ.