ค้นหาการใช้งานอัลกอริทึมใน Python

การดำเนินการค้นหาเป็นสิ่งที่ท้าทายอยู่เสมอ แต่ก็ใช่ว่าจะเป็นไปไม่ได้

ในชีวิตจริง เราจะค้นหาแบบไม่มีรูปแบบ เราแค่ไปที่ที่เราคิดว่าน่าจะวางอยู่ เราไม่ปฏิบัติตามรูปแบบใด ๆ ในกรณีส่วนใหญ่

สิ่งเดียวกันนี้ทำงานในโลกการเขียนโปรแกรมหรือไม่?

ไม่! ต้องมีรูปแบบการค้นหาสิ่งต่าง ๆ ในโปรแกรม เราจะเห็นอัลกอริทึมที่ทำตามรูปแบบต่างๆ สำหรับการค้นหาในบทความนี้

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

การค้นหาหมายถึงการค้นหาองค์ประกอบในอาร์เรย์ในบทความนี้

มาดูกันทีละคน

การค้นหาเชิงเส้น

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

เรามาแสดงอัลกอริทึมการค้นหาเชิงเส้นด้วยภาพประกอบที่น่าสนใจเพื่อความเข้าใจที่ดีขึ้นเกี่ยวกับอัลกอริทึม

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

มาดูการใช้งานอัลกอริทึมการค้นหาเชิงเส้นกัน

การดำเนินการค้นหาเชิงเส้น

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

มาดูขั้นตอนการปรับใช้อัลกอริทึมการค้นหาเชิงเส้นกัน

• เริ่มต้นอาร์เรย์ขององค์ประกอบ (หมายเลขนำโชคของคุณ)
• เขียนฟังก์ชันชื่อ search_element ซึ่งยอมรับสามอาร์กิวเมนต์ อาร์เรย์ ความยาวของอาร์เรย์ และองค์ประกอบที่จะค้นหา
• search_element(arr, n, องค์ประกอบ):
  • วนซ้ำอาร์เรย์ที่กำหนด
    • ตรวจสอบว่าองค์ประกอบปัจจุบันเท่ากับองค์ประกอบที่ต้องการหรือไม่
    • ถ้าใช่ก็คืนทรู
  • หลังจากเสร็จสิ้นการวนซ้ำ หากการดำเนินการยังคงอยู่ในฟังก์ชัน แสดงว่าองค์ประกอบนั้นไม่ปรากฏในอาร์เรย์ ดังนั้นกลับเป็นเท็จ
• พิมพ์ข้อความตามค่าส่งคืนของฟังก์ชัน search_element

สุดท้าย เขียนโค้ดด้วยความช่วยเหลือของขั้นตอนข้างต้นเพื่อใช้อัลกอริทึมการค้นหาเชิงเส้น

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

หากคุณทำไม่เสร็จ ไม่ต้องกังวล; ดูรหัสด้านล่างและเรียนรู้วิธีที่เรานำไปใช้ คุณจะได้รับโดยไม่ต้องใช้ความพยายามมาก

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

ขั้นแรก ให้รันโปรแกรมด้วยองค์ประกอบที่มีอยู่ในอาร์เรย์ และถัดไป ดำเนินการกับองค์ประกอบที่ไม่มีอยู่ในอาร์เรย์

ความซับซ้อนของเวลาของอัลกอริทึมการค้นหาเชิงเส้นคือ O(n)

เราสามารถลดมันลงอีกเล็กน้อยด้วยรูปแบบที่แตกต่างกันได้หรือไม่?

ใช่เราทำได้ มาดูกันเลย

การค้นหาไบนารี

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

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

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

ภาพประกอบช่วยให้เราเข้าใจอัลกอริทึมการค้นหาแบบไบนารีได้ดีขึ้น มาตรวจสอบกัน

ความซับซ้อนของเวลาของอัลกอริทึมการค้นหาแบบไบนารีคือ O(log n) ในการวนซ้ำแต่ละครั้ง ความยาวของพื้นที่ค้นหาจะลดลงครึ่งหนึ่ง มันกำลังลดลงอย่างทวีคูณ

การดำเนินการค้นหาแบบไบนารี

ขั้นแรก เราจะดูขั้นตอนในการใช้อัลกอริทึมการค้นหาแบบไบนารีและโค้ด มาดูขั้นตอนในการดำเนินการอัลกอริทึมการค้นหาแบบไบนารีให้เสร็จสมบูรณ์

• เริ่มต้นอาร์เรย์ด้วยองค์ประกอบ (หมายเลขนำโชคของคุณ)
• เขียนฟังก์ชันชื่อ search_element ซึ่งรับอาร์กิวเมนต์สามรายการ อาร์เรย์ที่เรียงลำดับ ความยาวของอาร์เรย์ และองค์ประกอบที่จะค้นหา
• search_element(sorted_arr, n, องค์ประกอบ):
  • เริ่มต้นตัวแปรดัชนี i สำหรับการวนซ้ำอาร์เรย์
  • ถัดไป เริ่มต้นตัวแปรสองตัวเพื่อรักษาพื้นที่การค้นหาของอาร์เรย์ ที่นี่เราเรียกว่าเริ่มต้นและสิ้นสุดตามที่ระบุดัชนี
  • วนซ้ำจนกว่า i จะน้อยกว่าความยาวของอาร์เรย์
    • คำนวณดัชนีกลางของพื้นที่ค้นหาโดยใช้ค่าเริ่มต้นและค่าสิ้นสุด จะเป็น (เริ่ม + จบ) // 2.
    • ตรวจสอบว่าองค์ประกอบดัชนีกลางจากพื้นที่ค้นหาเท่ากับองค์ประกอบที่ต้องการหรือไม่
    • ถ้าใช่ก็คืนทรู
    • มิฉะนั้น หากองค์ประกอบที่จัดทำดัชนีตรงกลางน้อยกว่าองค์ประกอบที่ต้องการ ให้ย้ายดัชนีเริ่มต้นของพื้นที่ค้นหาไปที่ตรงกลาง + 1
    • มิฉะนั้น หากองค์ประกอบที่จัดทำดัชนีตรงกลางมีค่ามากกว่าองค์ประกอบที่ต้องการ ให้ย้ายดัชนีสิ้นสุดของพื้นที่ค้นหาไปที่ตรงกลาง – 1
    • เพิ่มดัชนีของอาร์เรย์ i
  • หลังจากเสร็จสิ้นการวนซ้ำ หากการดำเนินการยังคงอยู่ในฟังก์ชัน แสดงว่าองค์ประกอบนั้นไม่ปรากฏในอาร์เรย์ ดังนั้นกลับเป็นเท็จ
• พิมพ์ข้อความตามค่าส่งคืนของฟังก์ชัน search_element

ลองเขียนโค้ดคล้ายกับการใช้อัลกอริทึมการค้นหาเชิงเส้น

…

คุณได้รับรหัส?

ใช่ เปรียบเทียบกับรหัสด้านล่าง ไม่ ไม่ต้องกังวล; ทำความเข้าใจการใช้งานด้วยรหัสด้านล่าง

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

ทดสอบโค้ดกับกรณีต่างๆ ที่มีองค์ประกอบอยู่และไม่มีอยู่ในบางกรณี

บทสรุป

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

ตอนนี้ คุณมีความรู้ที่ดีเกี่ยวกับอัลกอริทึมที่ใช้กันอย่างแพร่หลายใน Python

ต่อไป ค้นหาซอฟต์แวร์การค้นหาที่โฮสต์เองซึ่งเป็นที่นิยม

มีความสุขในการเขียนโค้ด 🙂 🧑‍💻