>> [MUSIC CHƠI]
>> DOUG LLOYD: Tất cả các quyền.
Vì vậy, tìm kiếm nhị phân là một thuật toán chúng ta có thể sử dụng
để tìm một phần tử bên trong một mảng.
Không giống như tìm kiếm tuyến tính, nó đòi hỏi một điều kiện đặc biệt được đáp ứng trước,
nhưng nó rất hiệu quả hơn nhiều nếu mà điều kiện là, trong thực tế, đáp ứng.
>> Vì vậy, ý tưởng ở đây là gì?
đó là phân chia và chinh phục.
Chúng tôi muốn giảm bớt kích thước của khu vực tìm kiếm một nửa mỗi lần
để tìm ra một số mục tiêu.
Đây là nơi mà điều kiện đến chơi, mặc dù.
Chúng tôi chỉ có thể tận dụng sức mạnh của loại bỏ một nửa của các yếu tố
mà thậm chí không nhìn vào họ nếu mảng được sắp xếp.
>> Nếu đó là một hỗn hợp hoàn chỉnh lên, chúng ta không thể chỉ ra khỏi bàn tay
loại bỏ một nửa trong số các yếu tố, vì chúng ta không biết những gì chúng ta vứt bỏ.
Nhưng nếu mảng được sắp xếp, chúng ta có thể làm điều đó, bởi vì chúng tôi
biết rằng tất cả mọi thứ để các trái của nơi chúng tôi đang có
được thấp hơn giá trị chúng tôi hiện tại.
Và tất cả mọi thứ để các quyền của chúng ta ở đâu
phải lớn hơn giá trị Hiện tại chúng tôi đang tìm kiếm.
>> Vì vậy, các mã giả là những gì các bước để tìm kiếm nhị phân?
Chúng tôi lặp lại quá trình này cho đến khi mảng hoặc, như chúng ta tiến hành thông qua,
mảng phụ, miếng nhỏ hơn các mảng ban đầu, có kích thước 0.
Tính trung điểm của mảng phụ hiện hành.
>> Nếu các giá trị mà bạn đang tìm kiếm là trong đó phần tử của mảng, dừng lại.
Bạn tìm thấy nó.
Thật tuyệt.
Nếu không, nếu mục tiêu là ít hơn so với những gì ở giữa,
do đó, nếu giá trị, chúng tôi đang tìm kiếm cho là thấp hơn so với những gì chúng ta thấy,
lặp lại quá trình này một lần nữa, nhưng thay đổi điểm kết thúc, thay vì
của là gốc hoàn thành mảng đầy đủ,
được chỉ sang bên trái của nơi mà chúng ta chỉ nhìn.
>> Chúng tôi biết rằng giữa là quá cao, hoặc các mục tiêu đã được ít hơn giữa,
và do đó, nó phải tồn tại, nếu nó tồn tại ở tất cả các mảng,
một nơi nào đó bên trái của trung điểm.
Và vì vậy chúng tôi sẽ thiết lập các mảng địa chỉ sang bên trái
trung điểm như điểm kết thúc mới.
Ngược lại, nếu mục tiêu là lớn hơn những gì ở giữa,
chúng tôi làm chính xác cùng quá trình, nhưng thay vào đó chúng tôi
thay đổi điểm khởi đầu là ngay bên phải của trung điểm
chúng ta chỉ cần tính toán.
Và sau đó, chúng tôi bắt đầu quá trình một lần nữa.
>> Hãy hình dung này, OK?
Vì vậy, có rất nhiều đi và về đây, nhưng đây là một mảng của 15 yếu tố.
Và chúng ta sẽ được theo dõi của rất nhiều các công cụ thời gian này.
Vì vậy, trong tìm kiếm tuyến tính, chúng tôi đã chỉ quan tâm đến một mục tiêu.
Nhưng lần này, chúng tôi muốn quan tâm đến nơi là chúng tôi
bắt đầu tìm kiếm ở đâu, Chúng ta dừng lại nhìn,
và trung điểm là những gì của mảng hiện hành.
Vì vậy, ở đây chúng tôi đi với tìm kiếm nhị phân.
Chúng tôi khá nhiều tốt để đi, phải không?
Tôi chỉ cần đi để đặt xuống dưới đây là một tập hợp các chỉ số.
Đây là yếu tố cơ bản chỉ là những gì của mảng, chúng tôi đang nói về.
Với tìm kiếm tuyến tính, chúng tôi quan tâm, bởi vì như chúng ta
cần phải biết có bao nhiêu yếu tố chúng ta lặp qua,
nhưng chúng tôi không thực sự quan tâm những gì yếu tố hiện tại chúng tôi đang tìm kiếm.
Trong cuộc tìm kiếm nhị phân, chúng ta làm.
Và do đó, những chỉ đó như là một hướng dẫn rất ít.
>> Vì vậy, chúng ta có thể bắt đầu, phải không?
Vâng, không khá.
Hãy nhớ những gì tôi nói về tìm kiếm nhị phân?
Chúng ta không thể làm điều đó trên một mảng được phân loại hoặc khác,
chúng tôi không đảm bảo rằng Các nguyên tố hoặc giá trị nhất định là không
là vô tình bỏ đi khi chúng ta chỉ
quyết định bỏ qua một nửa của mảng.
>> Vì vậy, bước một với tìm kiếm nhị phân là bạn phải có một mảng được sắp xếp.
Và bạn có thể sử dụng bất kỳ phân loại các thuật toán, chúng tôi đã nói chuyện về
để giúp bạn có được vị trí đó.
Vì vậy, bây giờ, chúng ta đang ở trong một vị trí mà chúng ta có thể thực hiện tìm kiếm nhị phân.
>> Vì vậy, hãy lặp lại quá trình từng bước và giữ
theo dõi những gì đang xảy ra khi chúng ta đi.
Vì vậy, đầu tiên chúng ta cần làm là tính toán trung điểm của các mảng hiện hành.
Vâng, chúng tôi sẽ nói rằng chúng ta, trước tất cả, tìm kiếm giá trị 19.
Chúng tôi đang cố gắng để tìm ra số 19.
Yếu tố đầu tiên của việc này mảng nằm ở chỉ số zero,
và yếu tố cuối cùng này mảng được đặt tại số 14.
Và vì vậy chúng tôi sẽ gọi cho những người bắt đầu và kết thúc.
>> Vì vậy, chúng tôi tính toán trung điểm của thêm 0 cộng với 14 chia cho 2;
trung điểm khá đơn giản.
Và chúng ta có thể nói rằng trung điểm hiện nay là 7.
Vậy là 15 gì chúng tôi đang tìm kiếm?
Không, nó không phải.
Chúng tôi đang tìm kiếm 19.
Nhưng chúng ta biết rằng 19 là lớn hơn so với những gì chúng tôi tìm thấy ở giữa.
>> Vì vậy, những gì chúng ta có thể làm là thay đổi điểm khởi đầu
để được ở ngay bên phải của trung điểm, và lặp lại quá trình này một lần nữa.
Và khi chúng ta làm điều đó, bây giờ chúng ta nói điểm khởi đầu mới là mảng vị trí 8.
Những gì chúng ta đã thực hiện có hiệu quả là tất cả mọi thứ bỏ qua bên trái của 15.
Chúng tôi đã loại bỏ một nửa của vấn đề, và bây giờ,
thay vì phải tìm kiếm hơn 15 phần tử trong mảng của chúng tôi,
chúng ta chỉ cần tìm kiếm trên 7.
Vì vậy, 8 là điểm khởi đầu mới.
14 vẫn là điểm kết thúc.
>> Và bây giờ, chúng tôi đi qua này một lần nữa.
Chúng tôi tính toán trung điểm mới.
8 cộng với 14 là 22, chia cho 2 là 11.
Đây có phải là những gì chúng tôi đang tìm kiếm?
Không, nó không phải.
Chúng tôi đang tìm kiếm một giá trị đó là ít hơn so với những gì chúng ta vừa được tìm thấy.
Vì vậy, chúng ta sẽ lặp lại quá trình một lần nữa.
Chúng tôi sẽ thay đổi điểm kết thúc là ngay bên trái của trung điểm.
Vì vậy, điểm kết thúc mới trở thành 10.
Và bây giờ, đó là phần duy nhất của mảng chúng ta phải sắp xếp thông qua.
Vì vậy, bây giờ chúng tôi đã loại bỏ 12 trong số 15 yếu tố.
Chúng tôi biết rằng nếu 19 tồn tại trong mảng, nó
phải tồn tại một nơi nào đó giữa phần tử số 8 và yếu tố số 10.
>> Vì vậy, chúng tôi tính toán trung điểm mới một lần nữa.
8 cộng với 10 là 18, chia cho 2 là 9.
Và trong trường hợp này, nhìn, mục tiêu là ở giữa.
Chúng tôi tìm thấy chính xác những gì chúng tôi đang tìm kiếm.
Chúng ta có thể dừng lại.
Chúng tôi đã hoàn thành công tìm kiếm nhị phân.
Được rồi.
Vì vậy, chúng ta biết thuật toán này hoạt động nếu mục tiêu là
một nơi nào đó bên trong của mảng.
Có hoạt thuật toán này nếu các mục tiêu không phải là trong mảng?
Vâng, chúng ta hãy bắt đầu nó một lần nữa, và lần này,
chúng ta hãy tìm kiếm các phần tử 16, mà trực quan chúng ta có thể nhìn thấy
không tồn tại bất cứ nơi nào trong mảng.
>> Điểm khởi đầu là một lần nữa 0.
Điểm cuối cùng là một lần nữa 14.
Đó là những chỉ số của các đầu tiên và phần tử cuối cùng của mảng hoàn chỉnh.
Và chúng ta sẽ đi qua các quá trình chúng ta chỉ đi qua một lần nữa, cố gắng để tìm thấy 16,
mặc dù trực quan, chúng ta có thể đã nói rằng nó sẽ không có mặt ở đó.
Chúng tôi chỉ muốn chắc chắn rằng thuật toán này sẽ, trên thực tế, vẫn còn làm việc trong một số cách
và không chỉ để lại cho chúng tôi bị mắc kẹt trong một vòng lặp vô hạn.
>> Vì vậy, bước đầu tiên là gì?
Tính trung điểm của mảng hiện hành.
Trung điểm là gì của mảng hiện tại?
Vâng, đó là 7, phải không?
14 cộng với 0 chia cho 2 là 7.
15 điều chúng ta đang tìm kiếm?
Không.
Nó khá gần, nhưng chúng tôi đang tìm kiếm cho một giá trị hơi lớn hơn thế.
>> Vì vậy, chúng ta biết rằng nó sẽ có nơi nào để trái 15.
Các mục tiêu lớn hơn những gì trong trung điểm.
Và vì vậy chúng tôi thiết lập điểm khởi đầu mới đến là ngay bên phải của giữa.
Trung điểm hiện nay là 7, do đó hãy nói rằng điểm khởi đầu mới là 8.
Và những gì chúng ta đã có hiệu quả thực hiện một lần nữa bị bỏ qua
toàn bộ nửa bên trái của mảng.
>> Bây giờ, chúng ta lập lại xử lý thêm một lần nữa.
Tính trung điểm mới.
8 cộng với 14 là 22, chia cho 2 là 11.
23 điều chúng ta đang tìm kiếm?
Tiếc là không có.
Chúng tôi đang tìm kiếm một giá trị đó là ít hơn 23.
Và như vậy trong trường hợp này, chúng ta sẽ để thay đổi điểm kết thúc là chỉ
bên trái của trung điểm hiện tại.
Trung điểm hiện tại là 11, và vì vậy chúng tôi sẽ thiết lập các điểm kết thúc mới
cho thời gian tới chúng tôi đi thông qua quá trình này đến 10.
>> Một lần nữa, chúng tôi đi qua quá trình này một lần nữa.
Tính trung điểm.
8 cộng với 10 chia cho 2 là 9.
19 điều chúng ta đang tìm kiếm?
Tiếc là không có.
Chúng tôi vẫn đang tìm kiếm một số ít hơn.
Vì vậy, chúng tôi sẽ thay đổi điểm kết thúc thời gian này là ngay bên trái của trung điểm.
Trung điểm hiện tại là 9, do đó, điểm cuối cùng sẽ là 8.
Và bây giờ, chúng tôi chỉ tìm tại một mảng yếu tố duy nhất.
>> Trung điểm của mảng này là gì?
Vâng, nó bắt đầu lúc 8, nó kết thúc vào 8, trung điểm là 8.
Đó là những gì chúng tôi đang tìm kiếm?
Có phải chúng ta đang tìm kiếm 17?
Không, chúng tôi đang tìm kiếm 16.
Vì vậy, nếu nó tồn tại trong mảng, nó phải tồn tại một nơi nào đó
bên trái của nơi chúng tôi đang có.
Vì vậy, những gì chúng ta sẽ làm gì?
Vâng, chúng tôi sẽ thiết lập các điểm kết thúc là chỉ bên trái của trung điểm hiện tại.
Vì vậy, chúng tôi sẽ thay đổi điểm kết thúc 7.
Bạn có thấy gì chỉ xảy ra ở đây, mặc dù?
Nhìn lên ở đây bây giờ.
>> Bắt đầu bây giờ là lớn hơn hết.
Hiệu quả, hai đầu các mảng của chúng tôi đã vượt qua,
và điểm khởi đầu là bây giờ sau khi các điểm kết thúc.
Vâng, điều đó không có thực hiện bất kỳ ý nghĩa, phải không?
Vì vậy, bây giờ, chúng ta những gì chúng ta có thể nói là có một mảng phụ kích thước 0.
Và một khi chúng ta nhận được đến thời điểm này, chúng tôi có thể bây giờ
đảm bảo yếu tố đó 16 không tồn tại trong mảng,
vì điểm khởi đầu và điểm kết thúc đã vượt qua.
Và do đó, nó không có ở đó.
Bây giờ, nhận thấy rằng điều này là hơi khác với điểm bắt đầu và kết thúc
chỉ là cùng.
Nếu chúng ta tìm kiếm 17, nó sẽ có
được trong mảng, và điểm khởi đầu và điểm kết thúc mà lặp cuối cùng
trước khi những điểm vượt qua, chúng ta sẽ tìm ra 17 đó.
Đó là chỉ khi họ qua đó chúng ta có thể đảm bảo rằng các phần tử không
tồn tại trong mảng.
>> Vì vậy, chúng ta hãy ít hơn rất nhiều bước so với tìm kiếm tuyến tính.
Trong trường hợp xấu nhất, chúng tôi đã có để chia tay một danh sách các yếu tố n
lặp đi lặp lại một nửa để tìm mục tiêu, hoặc vì các yếu tố mục tiêu
sẽ là một nơi nào đó ở cuối cùng chia, hoặc nó không tồn tại.
Vì vậy, trong trường hợp xấu nhất, chúng ta phải chia ra các array-- bạn có biết?
Nhật ký của n lần; chúng tôi phải cắt giảm các vấn đề
trong một nửa số lần nhất định.
Đó là số lần là log n.
>> Trường hợp kịch bản tốt nhất là gì?
Vâng, lần đầu tiên chúng ta tính trung điểm,
chúng ta tìm thấy những gì chúng tôi đang tìm kiếm.
Trong tất cả các trang trước ví dụ về tìm kiếm nhị phân
chúng tôi vừa đi qua, nếu chúng ta có được tìm kiếm các nguyên tố 15,
chúng ta sẽ thấy rằng ngay lập tức.
Đó cũng là lúc bắt đầu.
Đó là trung điểm của những nỗ lực đầu tiên tại một sự chia rẽ
của một bộ phận trong tìm kiếm nhị phân.
>> Và như vậy trong tồi tệ nhất trường hợp, tìm kiếm nhị phân chạy
trong log n, mà là tốt hơn đáng kể so với tìm kiếm tuyến tính, trong trường hợp xấu nhất.
Trong trường hợp tốt nhất, nhị phân tìm kiếm chạy trong omega của 1.
Vì vậy, tìm kiếm nhị phân là rất nhiều tốt hơn so với tìm kiếm tuyến tính,
nhưng bạn phải đối phó với quá trình phân loại các mảng của bạn đầu tiên trước khi bạn có thể
tận dụng sức mạnh của tìm kiếm nhị phân.
>> Tôi Doug Lloyd.
Đây là CS 50.