JavaScript ค้นหาไบนารี:คู่มือ

วิธีเขียนโค้ดการค้นหาแบบไบนารีใน JavaScript

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

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

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

มาสร้างอัลกอริทึมการค้นหาแบบไบนารีใน JavaScript!

การค้นหาแบบไบนารีคืออะไร

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

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

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

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

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

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

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

การค้นหาแบบไบนารีจะเข้าใจได้ง่ายเมื่อคุณเข้าใจแล้ว

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

อันดับแรก เราต้องหาเลขตรงกลางและกำหนดให้กับตัวแปร พบได้โดยการคำนวณผลรวมของตัวเลขตัวแรกและตัวสุดท้ายแล้วหารด้วยสอง เราจะเรียกตัวแปรนี้ว่า "กลาง":

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

ในตัวอย่างนี้ 8 ไม่เท่ากับ 9 การค้นหาของเราดำเนินต่อไป

ต่อไปเราต้องเปรียบเทียบว่าเลขกลางมากกว่า 9 หรือไม่ ไม่ใช่

สิ่งนี้บอกเราว่าตัวเลขที่เรากำลังค้นหาต้องอยู่หลังหมายเลขตรงกลาง 9 มากกว่า 8 ในรายการที่เรียงลำดับ เราจะตั้งค่าจำนวนเริ่มต้นของเราให้เท่ากับจำนวนตรงกลาง เนื่องจากเราทราบดีว่าจำนวนที่เรากำลังค้นหาไม่ได้มาก่อนเลขกลาง

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

การค้นหาไบนารีซ้ำอีกครั้งในครึ่งบนของรายการเนื่องจาก 9 มากกว่า 8:

เราพบเลขกลางอีกครั้ง นี่คือ 9 เราสามารถเปรียบเทียบ 9 กับตัวเลขที่เรากำลังค้นหา 9 เท่ากับจำนวนที่เราค้นหา

ซึ่งหมายความว่าการค้นหาของเราสามารถหยุดได้ เราพบหมายเลข 9 ในรายการของเราเรียบร้อยแล้ว!

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

การค้นหาแบบไบนารีสามารถดำเนินการได้โดยใช้วิธีการแบบวนซ้ำหรือแบบเรียกซ้ำ

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

การค้นหาไบนารีแบบวนซ้ำใช้การวนซ้ำ while เพื่อค้นหารายการในรายการ วนซ้ำนี้จะดำเนินการจนกว่าจะพบรายการในรายการหรือจนกว่าจะมีการค้นหารายการ

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

function binarySearch(array, numberToFind) {
	let start = 0;
	let end = array.length - 1;

	while (start <= end) {
		let middle = Math.floor((start + end) / 2);

		if (array[middle] === numberToFind) {
			return middle;
		} else if (array[middle] < numberToFind) {
			start = middle + 1;
		} else {
			end = middle - 1;
		}
	}

	return -1;
}

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

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

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

ฟังก์ชันของเรายังไม่ทำงาน เราต้องเขียนโปรแกรมหลักที่เรียกว่า:

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind);

if (findNumber !== -1) {
	console.log(`${toFind} has been found at position ${findNumber}.`);
} else {
	console.log(`${toFind} has not been found.`);
}

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

-1 หมายถึงไม่พบรายการ หากไม่พบรายการเนื้อหาของ else . ของเรา คำสั่งจะถูกดำเนินการ มิฉะนั้น เนื้อหาของ if คำสั่งถูกเรียกใช้

เรียกใช้รหัสของเรา:

9 has been found at position 3.

สิ่งนี้บอกเราว่าการค้นหาของเราประสบความสำเร็จ!

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

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

เปิดไฟล์ JavaScript ใหม่แล้ววางในโค้ดนี้:

function binarySearch(array, numberToFind, start, end) {
	if (start => end) {
		return -1;
	}

	let middle = Math.floor((start + end) / 2);

	if (array[middle] === numberToFind) {
		return middle;
	} else if (array[middle] < numberToFind) {
		return binarySearch(array, numberToFind, middle + 1, end);
	} else {
		return binarySearch(array, numberToFind, start, middle - 1);
	}
}

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

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

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

ในการเรียกใช้ฟังก์ชันนี้ เราจำเป็นต้องทำการเปลี่ยนแปลงในโปรแกรมหลักของเรา:

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1);
… 

เราจำเป็นต้องส่งผ่านพารามิเตอร์เพิ่มเติมสองรายการ:ค่าของ "เริ่มต้น" และ "สิ้นสุด" ค่าของ "เริ่มต้น" เท่ากับ 0 ค่าของ "สิ้นสุด" เท่ากับความยาวของรายการลบหนึ่ง

เรียกใช้โค้ดของเราแล้วดูว่าเกิดอะไรขึ้น:

9 has been found at position 3.

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

บทสรุป

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

ตอนนี้คุณพร้อมที่จะใช้งานการค้นหาแบบไบนารีใน JavaScript อย่างผู้เชี่ยวชาญแล้ว!