Làm sao để thuật toán binary search có thể tìm ra được nhiều vị trí?

[minhvunamdinh (mongmanh)]

mọi người cho mình hỏi là
trong một mảng có 2 phần tử giống nhau ở 2 vị trí khác nhau thì làm cách nào cho thuật toán binary có thể search ra được cả 2 vị trí,mình đã cố thử nhưng kết quả toàn cho ra 1 vị trí đầu tiên

[rogp10]

Cái này chỉ cần thay đổi cách nhìn 1 chút: giờ chia mảng thành hai phần theo x, vậy bạn chia ntn?

[TyE (Hà Mã Tím)]

binary search mảng đã được xếp sẵn vì vậy bạn chỉ cần lấy 1 lèo toàn bộ những ô giống nhau là được
Ví dụ bạn sẽ lấy được index chú hà mã đầu tiên, vậy thì tăng index lấy tiếp cho đến khi không còn hà mã nữa:

[TyE (Hà Mã Tím)]

để phủ được trường hợp này thì bạn cần chạy 2 loop, ví dụ như lấy được index của chú thứ 3 thì bạn cần 1 loop giảm index để bắt toàn bộ bên trái và 1 loop tăng index để bắt toàn bộ bên phải.
vậy là sẽ bắt được toàn bộ 5 .

[nitro2 (Nhím)]

Mọi người đừng bị chủ thớt lừa.
Thực ra đề là:
“Cho một mảng các số nguyên các số khác nhau đôi một, chỉ duy nhất 1 cặp trùng nhau. Tìm cặp số đó”
Chủ thớt nghĩ rằng dùng binary search sẽ ra nên hỏi vậy.
Ahihi, đoán đại vậy thôi.

[library (La biblioteca)]

ủa làm được vậy à? Hay vậy?

[hungaya (Hung)]

Dùng chia để trị thôi, chia như phần chia partition của QuickSort ấy.

Mà thớt sao có thể nhầm phần tạo partition thành binary search hay vậy?

[nitro2 (Nhím)]

@library

ủa làm được vậy à? Hay vậy?

@hungaya

Mà thớt sao có thể nhầm phần tạo partition thành binary search hay vậy?

Nếu làm được thì lên đây hỏi làm giề

[tntxtnt]

@minhvunamdinh

trong một mảng có 2 phần tử giống nhau ở 2 vị trí khác nhau thì làm cách nào cho thuật toán binary có thể search ra được cả 2 vị trí, mình đã cố thử nhưng kết quả toàn cho ra 1 vị trí đầu tiên

đề yêu cầu tìm chỉ 2 phần tử thôi à?
đề cho mảng đã sắp xếp chưa mà xài binary search?
nếu đã sắp xếp rồi, tìm được vị trí phần tử đầu tiên thì phần tử thứ 2 ở ngay cạnh nó chứ ở đâu nữa >_>

[phamdat2 (Phạm Tiến Đạt)]

mọi người cho mình hỏi là
trong một mảng có 2 phần tử giống nhau ở 2 vị trí khác nhau thì làm cách nào cho thuật toán binary có thể search ra được cả 2 vị trí,mình đã cố thử nhưng kết quả toàn cho ra 1 vị trí đầu tiên

• nếu bạn vẫn kiên quyết dùng binary search thì nó sẽ nằm ở bên trái hoặc phải của cái vị trí, tùy RNG của bạn như nào :v (tất nhiên là yêu cầu của binary search là mảng phải được sắp xếp)
• hoặc có thể dùng cái này

[rogp10]

Mảng nhiều phần tử đó thì thành O(n) chia mảng làm đôi là chắc cú.

Nhưng do đặc điểm này nên ta có thể tìm kiếm theo kiểu ±1, ±2, ±4, ±8…

[Lam_Tung2 (Lâm Tùng)]

• Cách đơn giản nhất là duyệt từ đầu mảng đến cuối mảng a[i] = key thì vứt i vào stack nào đó.Độ phức tạp O(n).
• Nếu mảng đã sắp xếp rồi thì ý tưởng là dùng binary_search nhưng vấn đề là binary_search cần phải cải tiến cho 2 nhiệm vụ dùng để tìm vị trí đầu tiên sao cho giá trị = key và một biến thể # của binary_search để đếm tất cả phần tử key trong mảng.Độ phức tập O(log n).

[nitro2 (Nhím)]

@Lam_Tung2

a[i] = key thì vứt i vào stack nào đó

key ở đâu ra vậy bạn?

[hungaya (Hung)]

Thật ra bài này dùng thuật toán Rùa và Thỏ như bạn Đạt đưa link là tối ưu nhất. Nhưng thớt đang cố áp dụng 1 thuật toán có dạng binary search để giải.

[Pham_Xuan (Phạm Viết Xuân)]

Binary search chỉ dùng được với mảng đã sắp xếp rồi. Vì vậy các phần tử bằng nhau luôn đứng kề nhau. Chỉ cần tìm được vị trí đầu tiên rồi cho 1 vòng lặp là biết được tất cả vị trí có giá trị bằng nhau rồi còn gì.

[nitro2 (Nhím)]

@nitro2

Thực ra đề là:
“Cho một mảng các số nguyên các số khác nhau đôi một, chỉ duy nhất 1 cặp trùng nhau. Tìm cặp số đó”

[HR16 (Gà Coder)]

Đúng cái video mình từng xem luôn =]]