Tìm kiếm một phần tử trong log (n) thời gian

Question

Tôi đã xem qua những câu dưới đây:

Giả sử tôi sửa đổi một danh sách được sắp xếp cho các con số khác biệt 4n như sau:

Giữ yếu tố trong thậm chí vị trí (vị trí 2, 4, 6, ... 4n). Hình thành các cặp phân tách n (i, j) trên các vị trí số lẻ trong đó i = 2k + 1 cho một số k = 0 đến n -1 và j = 2k + 1 cho một số k = n đến 2n − 1.

Bây giờ hoán đổi các phần tử ở các vị trí i và j cho mỗi cặp như vậy. (tức là mọi phần tử trong một vị trí được đánh số lẻ trong nửa đầu của mảng được hoán đổi với một số phần tử ở một vị trí được đánh số lẻ trong nửa thứ hai của mảng. Không có phần tử nào tham gia vào nhiều trao đổi (tức là các giao dịch hoán đổi được phân tách) Bạn không biết những cặp (i, j) này ngoại trừ một phần tử ở một vị trí được đánh số lẻ trong nửa đầu của mảng được hoán đổi với một số phần tử ở một vị trí được đánh số lẻ trong nửa thứ hai. giải thích cách bạn có thể xác định xem liệu x có nằm trong mảng (mới được chỉnh sửa) trong thời gian O (logn) hay không.

Thành thật mà nói, tôi không chắc chắn về cách tiếp cận mảng này. nó tồn tại ở bất kỳ vị trí được đánh số nào bằng cách sử dụng tìm kiếm nhị phân.Nhưng các số ở các vị trí lẻ không còn được sắp xếp.

Bất kỳ trợ giúp nào được đánh giá cao. Cảm ơn!

Answer 1

Bạn có thể xác định xem một số thành phần x có trong bộ mới (xáo trộn) bằng cách thực hiện hai tìm kiếm nhị phân hay không. Chìa khóa ở đây là các phần tử lẻ cơ bản hoạt động như "các khóa" cho nhau, vì chúng đã được hoán đổi trong các cặp rời nhau.

1. Sử dụng tìm kiếm nhị phân tiêu chuẩn để tìm kiếm x, đảm bảo rằng bạn luôn chọn thậm chí chỉ số để so sánh. (Sử dụng các chỉ số thậm chí là rất quan trọng, bởi vì đó là những yếu tố vẫn còn trong trật tự.)

2. Nếu x nằm trong mảng ở một chỉ số đồng đều, nó sẽ được tìm thấy. Nếu không, chúng tôi cuối cùng sẽ tìm thấy hai yếu tố m và n sao cho m < x < n và index(n) - index(m) == 2. Điều này có nghĩa là nếu mảng vẫn được sắp xếp, x sẽ phải là phần tử giữa m và n (nếu nó nằm trong mảng).

3. Xem xét phần tử ở chỉ mục giữa m và n - gọi số này y. Nếu phần tử x nằm trong mảng ban đầu, nó phải được đổi chỗ với y khi tạo mảng xáo trộn.

4. Thực hiện tìm kiếm nhị phân thứ hai để tìm kiếm y, một lần nữa đảm bảo bạn chỉ chọn thậm chí chỉ mục để so sánh. Tương tự như bước 2, cuối cùng bạn sẽ tìm thấy hai phần tử m' và n' sao cho m' < y < n' và index(n') - index(m') == 2. Nếu mảng vẫn được sắp xếp, phần tử y sẽ là phần tử giữa m' và n'.

5. Yếu tố giữa m' và n' phải bất cứ yếu tố đã được hoán đổi với y, và do đó bất cứ yếu tố ban đầu giữa m và n. Nếu giá trị này không phải là x thì x không tồn tại trong mảng.