tailieunhanh - 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ìm Nế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 | KỸ THUẬT LẬP TRÌNH TÌM KIẾM VÀ SẤP XÉP 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ìm Nếu bằng thì tìm thấy Nếu phần tử cần tìm phần tử giữa middle tìm trên nửa đầu tiên của mảng Nếu giá trị phần tử cần tìm giá trị phần tử giữa thì tìm ưên nửa sau của mảng Lặp lại - Rất nhanh thực hiện n bước đối với mảng 2n số phần tử của mảng 30 phần tử thực hiện frong 5 bước - 25 30 do vậy mất 5 bước Ví dụ Cho mảng a 100 phần từ đọc phần tử searchKey từ bàn phím. Viết chưong trình tìm kiếm phần tử searchKey trên mảng a theo kiểu tuyến tính 2 Tìm kiếm trên mảng 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 1 Fig. 2 Linear search of an array 3 include 4 define SIZE 100 5 6 function prototype 7 int linearSearch const int arrayE int key int size 8 9 function main begins program execution 10 int mainO 11 12 int a SIZE create array a 13 int x counter 14 int searchKey value to locate in a 15 int element variable to hold location of searchKey or -1 16 17 create data 18 for X 0 X SIZE X 19 a X 2 x 20 end for 21 22 printf Enter integer search key n 23 scanfC d ÃsearchKey 24 attempt to locate searchKey in array a 26 element 1inearsearchf a searchKey SIZE 27 28 display results 29 if c element -1 30 printfC Found value in element d n element 31 end if 32 else 33 printf value not found n 34 end else 35 36 return 0 indicates successful termination 37 38 end main 39 40 compare key to every element of array until the location is found 41 or until the end of array is reached return subscript of element 42 if key or -1 if key is not found 43 int linearsearchC const int arrayE int key int size 44 45 int n counter 46 47 loop through array 48 for c n 0 n size n 49 1 Fig. 2 Binary search of an array 3 include 4 define SIZE 15 5 6 function .