kỹ thuật lập trình: Tìm kiếm trên mảng

Tìm kiếm nhị phân: Đối với các mảng đã được sắp xếp – So sánh giá trị phần tử giữa với phần tử cần tìmNếu bằng thì tìm thấy • Nếu phần tử cần tìm giá trị phần tử giữa, thì tìm trên nửa sau
Nội dung trích xuất từ tài liệu:
kỹ thuật lập trình: Tìm kiếm trên mảng Tìm kiếm trên mảng KỸ THUẬT LẬP TRÌNH TÌM KIẾM VÀ SẮP XẾP • Tìm kiếm trên mảng: theo giá trị phần tử • Tìm kiếm tuyến tính – Đơn giản – So sánh các phần tử của mảng với giá trị phần tử cần tìm – Thường sử dụng cho mảng ít phần tử và chưa sắp xếp 0 1 1 /* Fig. 6.18: fig06_18.c 2 Linear search of an array */ Tìm kiếm trên mảng 3 #include 4 #define SIZE 100 5 • Tìm kiếm nhị phân 6 /* function prototype */ 7 int linearSearch( const int array[], int key, int size ); – Đối với các mảng đã được sắp xếp 8 – So sánh giá trị phần tử giữa với phần tử cần tìm 9 /* function main begins program execution */ 10 int main() • Nếu bằng thì tìm thấy 11 { • Nếu phần tử cần tìm < phần tử giữa (middle), tìm trên nửa đầu 12 int a[ SIZE ]; /* create array a */ 13 int x; /* counter */ tiên của mảng 14 int searchKey; /* value to locate in a */ • Nếu giá trị phần tử cần tìm > giá trị phần tử giữa, thì tìm trên 15 int element; /* variable to hold location of searchKey or -1 */ nửa sau của mảng 16 17 /* create data */ • Lặp lại 18 for ( x = 0; x < SIZE; x++ ) { – Rất nhanh; thực hiện n bước đối với mảng 2n > số phần tử 19 a[ x ] = 2 * x; 20 } /* end for */ của mảng 21 • 30 phần tử thực hiện trong 5 bước 22 printf( Enter integer search key: ); 23 scanf( %d, &searchKey ); – 25 > 30 do vậy mất 5 bước 24Ví dụ: Cho mảng a, 100 phần từ, đọc phần tử searchKey từ bàn phím. Viếtchương trình tìm kiếm phần tử searchKey trên mảng a theo kiểu tuyến tính 225 50 /* attempt to locate searchKey in array a */ if ( array[ n ] == key ) {26 51 element = linearSearch( a, searchKey, SIZE ); return n; /* return location of key */27 52 } /* end if */28 /* display results */ 5329 if ( element != -1 ) { 54 } /* end for */30 printf( Found value in element %d , element ); 5531 } /* end if */ 56 return -1; /* key not found */32 else { 5733 printf( Value not found ); ...