Tìm kiếm nhị phân - Short

Question 1

Nhắc nhở:
Tìm kiếm nhị phân mảng phải được sắp xếp

Question 2

0:19
» Vậy ý tưởng ở đây là gì?
0:20
đó là chia rẽ và chinh phục.

Question 3

Trong tìm kiếm nhị phân, ý tưởng của thuật toán là chia để trị, giảm một nửa diện tích tìm kiếm mỗi lần, cố gắng tìm một số mục tiêu.
Tuy nhiên, để tận dụng sức mạnh này, trước tiên mảng của chúng ta phải được sắp xếp, nếu không chúng ta không thể đưa ra các giả định về nội dung của mảng.

Question 4

Mã giả:
Repeat until the (sub)array is of size 0:
Calculate the middle point of the current (sub)array.
If the target is at the middle, stop.
Otherwise, if the target is less than what’s at the middle, repeat, changing the end point to be just to the left of the middle.
Otherwise, if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle.

Answer 4

Lặp lại cho đến khi mảng (con) có kích thước 0:
Tính điểm giữa của mảng (phụ) hiện tại.
Nếu mục tiêu ở giữa, dừng lại.
Ngược lại, nếu mục tiêu nhỏ hơn điểm ở giữa, hãy lặp lại, thay đổi điểm cuối thành ngay bên trái của điểm giữa.
Ngược lại, nếu mục tiêu lớn hơn điểm ở giữa, hãy lặp lại, thay đổi điểm bắt đầu thành ngay bên phải của điểm giữa.

Question 5

Trường hợp xấu nhất: Chúng ta phải chia đôi danh sách n phần tử nhiều lần để tìm phần tử đích, vì phần tử đích sẽ được tìm thấy ở cuối lần chia cuối cùng hoặc hoàn toàn không tồn tại trong mảng.
Trường hợp tốt nhất: Phần tử mục tiêu nằm ở điểm giữa của toàn bộ mảng và vì vậy chúng ta có thể ngừng tìm kiếm ngay sau khi bắt đầu.

Question 6

O(log n)
Ω(1)