Searching: linear and binary · การค้นหา: Linear และ Binary
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
วิธีการค้นหาสองแบบ
- การค้นหา หมายความว่าหาว่าค่าอยู่ที่ไหนในอาร์เรย์ (หรือบอกว่าไม่มีอยู่)
- Linear search ตรวจสอบทุกรายการทีละตัว ใช้งานได้กับอาร์เรย์ทุกชนิด
- Binary search เร็วกว่ามากแต่ต้องการให้-array被 sorted ก่อน
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
การค้นหาแบบเชิงเส้น
- เดินจากดัชนี
0ไปยังn - 1โดยเปรียบเทียบแต่ละรายการกับเป้าหมาย - คืนค่าดัชนีทันทีที่พบ ถ้าถึงจุดสิ้นสุด ให้คืนค่า
-1 - สำหรับ-array有
nรายการ วิธีนี้จะตรวจสอบสูงสุดถึงnรายการ
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
ทำไมการจัดเรียงจึงทำให้ binary search เป็นไปได้
- ถ้า-array被 sorted คุณสามารถกระโดดไปที่ กลาง และเปรียบเทียบได้
- ถ้าค่าตรงกลางเล็กเกินไป เป้าหมายต้องอยู่ในครึ่งขวา; ถ้าใหญ่เกินไป อยู่ครึ่งซ้าย
- ทุกขั้นตอนจะทิ้ง ครึ่ง ของ-array出，所以非常快（大约
log2(n)步）
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
low, high, mid
- รักษาสองขอบเขต:
low(เริ่มต้น) และhigh(สิ้นสุด) ค่าตรงกลางคือmid = low + (high - low) / 2 - ถ้า
a[mid]เป็นเป้าหมาย ให้คืนค่าmid. ถ้าa[mid] < target, ย้ายlow = mid + 1; มิฉะนั้นhigh = mid - 1 - หยุดเมื่อ
low > high— เป้าหมายไม่มีอยู่ ดังนั้นคืนค่า-1
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
ข้อผิดพลาดที่พบบ่อย
- Binary search ต้องใช้ array ที่ เรียงลำดับแล้ว
- Linear search ตรวจสอบแต่ละองค์ประกอบตามลำดับ
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
ลองดูเลย
- สำหรับ Binary Search ให้สมมติว่าอาร์เรย์ถูกเรียงลำดับไว้แล้ว ใช้
low,highและmid - คืนค่า
-1เมื่อไม่พบค่านั้น อย่า เขียนmain— ตัวตรวจสอบจะสร้างให้
Linear vs binary search · การค้นหาเชิงเส้นเทียบกับ binary search
Binary search halves the range each step. · Binary search ตัดช่วงเหลือครึ่งหนึ่งในแต่ละขั้นตอน
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not write a main. · เติม int linear_search(const int a[], int n, int target) ส่งค่า index ของ target ตัวแรก หรือ -1 ถ้าไม่มีใน array ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not write a main. · เติม int binary_search(const int a[], int n, int target) สำหรับ sorted array. คืนดัชนีของ target, หรือ -1. ใช้ low, high และ mid. ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not write a main. · เติม int first_negative(const int a[], int n) ส่งค่า index ของรายการแรกที่น้อยกว่า 0 หรือ -1 ถ้าไม่มี ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่