Thuật toán tìm kiếm nhị fân sử dụng kĩ thuật chia để trị để tìm kiếm. Đầu tiên, fần tử tìm kiếm được so sánh với phần tử giữa của list. Nếu fần tử tìm kiếm bé hơn phần tử giữa, giới hạn tìm kiệm lại về nửa đầu của list. Nếu không, tìm kiếm nửa sau của list. | Binary Search (Tìm kiếm nhị fân) Thuật toán tìm kiếm nhị fân sử dụng kĩ thuật chia để trị để tìm kiếm. Đầu tiên, fần tử tìm kiếm được so sánh với phần tử giữa của list. Nếu fần tử tìm kiếm bé hơn phần tử giữa, giới hạn tìm kiệm lại về nửa đầu của list. Nếu không, tìm kiếm nửa sau của list. Binary Search Tìm kiếm nhị fân là 1 kỹ thuật mạnh đáng kinh ngạc để tìm kiếm trong 1 list đã được sắp xếp. Nó quen thuộc với mọi người sử dụng danh bạ điện thoại. Minh họa Tìm kiếm với key = 78: 1 3 5 6 10 11 14 25 26 40 41 78 - (Xem hình minh hoạ trong slide tiếng anh) - 4 phép toán cần thiết để tìm ra phần tử fù hợp. - Thử tính xem phải dùng bao nhiêu phép toán nếu sử dụng tìm kiếm tuần tự? Ví dụ Đầu tiên so sánh 78 với fần tử giữa của list L[5] là 11. 78 > 11. Vì vậy ta giới hạn lại tìm kiếm L[6 11] như hình minh hoạ. Binary Search Code // target là số cần tìm, size là kích thước list Int binSearch (int List[], int Target, int Size) { int Mid, Lo = 0, Hi = Size –1; while( Lo 11. Vì vậy ta giới hạn lại tìm kiếm L[6 11] như hình minh hoạ. Binary Search Code // target là số cần tìm, size là kích thước list Int binSearch (int List[], int Target, int Size) { int Mid, Lo = 0, Hi = Size –1; while( Lo #define NotFound (-1) typedef int ElementType; int BinarySearch(ElementType A[ ], ElementType X, int N ) { int Low, Mid, High; Low = 0; High = N -1; while( Low X ) High = Mid -1; else return Mid; /* Found */ } return NotFound; /* NotFound được định nghĩa = -1 */ } Chương trình test main( ) { static int A[ ] = { 1, 3, 5, 7, 9, 13, 15 }; int SizeofA = sizeof( A ) / sizeof( A[ 0 ] ); int i; for( i = 0; i High) .
