Binary Search Python:คำแนะนำทีละขั้นตอน

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

คุณจะค้นหาตำแหน่งของรายการในรายการได้อย่างไร? การค้นหาแบบไบนารีช่วยคุณได้ โดยใช้การค้นหาแบบไบนารี คุณสามารถค้นหาตำแหน่งขององค์ประกอบภายในอาร์เรย์ที่จัดเรียงได้อย่างง่ายดาย

คอมพิวเตอร์สามารถค้นหารายการต่างๆ เพื่อค้นหารายการเฉพาะได้ดี กฎที่คอมพิวเตอร์ใช้เพื่อค้นหารายการในรายการเรียกว่าอัลกอริธึมการค้นหา อัลกอริธึม Python ที่ได้รับความนิยมมากที่สุดตัวหนึ่งคือการค้นหาแบบไบนารี

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

การค้นหาไบนารีของ Python คืออะไร

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

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

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

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

81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้

ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก

Binary Search Tree Python:ทีละขั้นตอน

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

เราจะค้นหาหมายเลข “22” ในรายการของเรา

ในการเริ่มต้น เราจะตั้งค่าตัวชี้สองตัวในรายการของเรา ตัวชี้หนึ่งจะแสดงค่าสูงสุดในรายการ และอีกจุดหนึ่งจะแสดงค่าต่ำสุด:

ต่ำ				สูง
7	9	14	22	34

ขั้นตอนต่อไปของเราคือการหาองค์ประกอบตรงกลางในอาร์เรย์ ซึ่งก็คือ 14 หากค่านี้เท่ากับค่าที่เรากำลังค้นหา ค่านี้ควรถูกส่งกลับ

ในกรณีนี้ 14 ไม่ใช่ 22 ดังนั้นโปรแกรมของเราจำเป็นต้องทำการเปรียบเทียบ

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

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

		ต่ำ	กลาง	สูง
7	9	14	22	34

เราพบค่ากลางของเราแล้ว โปรแกรมของเราจะคืนค่าตำแหน่งดัชนีของตัวเลขนั้น ในกรณีนี้ ตำแหน่งดัชนีของ 22 คือ 3 (โปรดจำไว้ว่า รายการจะถูกสร้างดัชนีโดยเริ่มที่ 0!)

วิธีการใช้การค้นหาแบบไบนารีใน Python

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

การค้นหาไบนารีแบบวนซ้ำใน Python

เราจะเริ่มต้นด้วยวิธีการวนซ้ำ นี่คือที่ที่เราจะวนรอบทุกรายการในรายการของเรา จากนั้นเราจะพบค่ากลางในรายการ เราจะทำต่อไปจนกว่าจะพบคุณค่าที่เราต้องการ

ฟังก์ชันการค้นหาไบนารี

เริ่มต้นด้วยการกำหนดฟังก์ชัน Python สำหรับการค้นหาไบนารีของเรา:

def findValue(numbers, number_to_find):
	low = 0
	high = len(listnumbers - 1

	while low <= high:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			low = middle + 1
		else:
			high = middle - 1
	return -1

ฟังก์ชันของเรายอมรับพารามิเตอร์ 2 ตัว ได้แก่ รายการที่เราต้องการค้นหา และตัวเลขที่เราต้องการค้นหาในรายการของเรา

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

ขั้นตอนต่อไปของเราคือการประกาศ Python while loop วนรอบนี้ทำงานในขณะที่องค์ประกอบต่ำสุดมีขนาดเล็กกว่าหรือเท่ากับจำนวนสูงสุด ซึ่งหมายความว่าการวนซ้ำของเราจะรันก็ต่อเมื่อยังไม่พบหมายเลขของเรา

จากนั้นเราคำนวณจำนวนตรงกลาง เราทำสิ่งนี้โดยการลบค่าต่ำสุดออกจากค่าสูงสุด จากนั้นเราคำนวณโมดูโล (ส่วนที่เหลือ) ของตัวเลขนั้นเมื่อหารด้วย 2 จากนั้นเราเพิ่มโมดูโลให้กับค่าของตัวเลขที่ต่ำที่สุด

หากหมายเลขตรงกลางในรายการของเราตรงกับตัวเลขที่เราต้องการค้นหา เราจะคืนค่าตำแหน่งของหมายเลขนั้น

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

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

ทำซ้ำจนต่ำเท่ากับหรือน้อยกว่าสูง หากไม่พบค่าของเรา เราจะคืนค่า -1 เราจะพูดถึงเหตุผลในอีกสักครู่

ดำเนินการค้นหา

เพิ่มรหัสต่อไปนี้ที่ด้านล่างของโปรแกรมของคุณ นอก findValue ฟังก์ชัน:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

เราเริ่มต้นด้วยการประกาศรายการสิ่งของที่เราต้องการค้นหา จากนั้นเราได้ระบุตัวเลขที่ต้องการหาคือ 22

ต่อไป เราเรียก findValue() . ของเรา และส่งต่อรายการ

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

มิฉะนั้น โปรแกรมของเราจะพิมพ์ข้อความแจ้งตำแหน่งดัชนีของค่านั้นให้เราทราบ

รหัสของเราส่งคืน:

The number 22 was found at index position 3.

ตอนนี้เรารู้แล้วว่าเลข 22 ปรากฏขึ้นที่ตำแหน่งดัชนี 3

การค้นหาไบนารีแบบเรียกซ้ำใน Python

เรายังสามารถใช้การเรียกซ้ำเพื่อทำการค้นหาแบบไบนารี นี่คือที่ที่เราจะกำหนดฟังก์ชันที่เรียกตัวเองไปเรื่อยๆ จนกว่าจะพบเงื่อนไข – ตัวเลขของเราถูกพบ

กำหนดฟังก์ชันแบบเรียกซ้ำ

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

def findValue(numbers, number_to_find, low, high):
	if high >= low:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			return findValue(numbers, number_to_find, middle + 1, high)
		else:
			return findValue(numbers, number_to_find, low, middle - 1)
	
	else:
		return -1

รหัสของเราค่อนข้างคล้ายกับตัวอย่างที่แล้ว

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

เราคำนวณเลขตรงกลางโดยใช้วิธีการเดียวกับในตัวอย่างที่แล้ว อันดับแรก เราลบค่าต่ำสุดจากค่าสูงสุด จากนั้น เราคำนวณโมดูโล (ส่วนที่เหลือ) ของค่านั้นเมื่อหารด้วย 2 สุดท้าย เราก็บวกตัวเลขที่ต่ำที่สุด

จากนั้นเราก็เขียน if คำสั่งที่ตัดสินว่าการค้นหาไบนารีของเราควรดำเนินการอย่างไร:

หากหมายเลขตรงกลางเท่ากับหมายเลขที่เรากำลังมองหา ตำแหน่งของหมายเลขนั้นจะถูกส่งคืน
ถ้าตัวเลขตรงกลางน้อยกว่าที่เรากำลังมองหา findValue() ของเรา ฟังก์ชันถูกเรียกอีกครั้ง คราวนี้ค่า ต่ำ ถูกกำหนดให้มีค่ามากกว่าค่ากลางของเราหนึ่งค่า
หากตัวเลขตรงกลางมากกว่าตัวเลขที่เรากำลังมองหา findValue() เรียกว่าฟังก์ชัน ค่าของ “สูง” จะเท่ากับค่าที่น้อยกว่าค่ากลางหนึ่งค่า

เขียนโปรแกรมหลัก

สิ่งที่เราต้องทำคือเขียนโปรแกรมหลักของเรา:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find, 0, len(numbers) - 1)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

โปรแกรมหลักของเราเหมือนกับตัวอย่างก่อนหน้าของเราแถบหนึ่งความแตกต่าง เรากำลังส่งพารามิเตอร์ใหม่สองตัวไปยัง findValue() . ของเรา ฟังก์ชั่น:ต่ำและสูง

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

รหัสของเราส่งคืน:

The number 22 was found at index position 3.

เราได้รับผลเช่นเดียวกันจากก่อนหน้านี้ ในตัวอย่างนี้ เราใช้โปรแกรมแบบเรียกซ้ำแทนโปรแกรมแบบวนซ้ำเพื่อทำการค้นหาแบบไบนารีของเรา

เมื่อใดที่คุณควรใช้ Python Binary Search

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

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

การค้นหาไบนารีในรายละเอียดความซับซ้อนของ Python

ความซับซ้อนของการค้นหาไบนารีคืออะไร? เป็นคำถามที่ดี

อัลกอริธึมการค้นหาแบบไบนารีมีความซับซ้อนของตัวพิมพ์ที่ดีที่สุดของ O(1) กรณีนี้เกิดขึ้นเมื่อการเปรียบเทียบครั้งแรกเท่ากับรายการที่คุณกำลังค้นหา

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

บทสรุป

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

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

ทุกครั้งที่ทำการค้นหา จำนวนตัวเลขที่โปรแกรมต้องค้นหาจะลดลงครึ่งหนึ่ง

หากต้องการเรียนรู้เพิ่มเติมเกี่ยวกับ Python โปรดอ่านคู่มือ How to Learn Python