>> ROB Bowden: Xin chào, tôi Rob.
Làm thế nào để chúng tôi sử dụng tìm kiếm nhị phân?
Hãy tìm hiểu.
Vì vậy, lưu ý rằng tìm kiếm này chúng ta sẽ thực hiện đệ quy.
Bạn cũng có thể thực hiện tìm kiếm nhị phân lặp đi lặp lại, vì vậy nếu bạn đã làm điều đó,
đó là hoàn toàn tốt đẹp.
>> Bây giờ đầu tiên, chúng ta hãy nhớ những gì các thông số để tìm kiếm được có nghĩa là phải.
Ở đây, chúng ta thấy giá trị int, đó là nghĩa vụ phải được các giá trị người dùng
tìm kiếm.
Chúng ta thấy các mảng int giá trị, mà là mảng mà chúng ta đang
tìm kiếm giá trị.
Và chúng ta thấy int n, đó là chiều dài của mảng của chúng tôi.
>> Bây giờ, điều đầu tiên đầu tiên.
Chúng tôi kiểm tra xem nếu n bằng 0, trong trường hợp mà chúng tôi trả về false.
Đó chỉ nói rằng nếu chúng ta có một sản phẩm nào mảng, giá trị rõ ràng là không trong một
mảng sản phẩm nào, vì vậy chúng tôi có thể trả về false.
>> Bây giờ, chúng tôi thực sự muốn làm nhị phân phần tìm kiếm của tìm kiếm nhị phân.
Vì vậy, chúng tôi muốn tìm giữa phần tử của mảng này.
Ở đây, chúng ta nói giữa bằng n chia 2, vì các yếu tố trung là
sẽ được chiều dài của mảng của chúng tôi chia cho 2.
Bây giờ chúng ta sẽ kiểm tra xem nếu yếu tố trung bằng giá trị chúng tôi
tìm kiếm.
Vì vậy, nếu giá trị trung bằng giá trị, chúng tôi có thể trở lại đúng kể từ khi chúng tôi tìm thấy
giá trị trong mảng của chúng tôi.
>> Nhưng nếu đó là không đúng sự thật, bây giờ chúng ta cần phải làm đệ quy
bước của tìm kiếm nhị phân.
Chúng tôi cần phải tìm kiếm hoặc đến trái của mảng hoặc các
giữa mảng.
Vì vậy, ở đây, chúng ta nói nếu giá trị ở giữa là thấp hơn giá trị, có nghĩa là giá trị mà
lớn hơn giữa của mảng.
Vì vậy, giá trị phải là ở bên phải của yếu tố mà chúng ta chỉ nhìn vào.
>> Vì vậy, ở đây, chúng ta sẽ tìm kiếm đệ quy.
Và chúng tôi sẽ nhìn vào những gì chúng tôi đang đi qua với điều này trong một giây.
Nhưng chúng ta sẽ tìm đến bên phải của phần trung lưu.
Và trong trường hợp khác, có nghĩa là giá trị thấp hơn giữa
mảng, và do đó chúng ta sẽ để tìm kiếm bên trái.
Bây giờ, bên trái là có được một chút dễ dàng hơn để xem xét.
Vì vậy, chúng ta thấy ở đây là chúng ta đệ quy kêu gọi tìm kiếm nơi đầu tiên
đối số là, một lần nữa, giá trị chúng tôi đang tìm kiếm hơn.
Đối số thứ hai là có được các mảng mà chúng tôi đã tìm kiếm trên.
Và yếu tố cuối cùng bây giờ là giữa.
Hãy nhớ rằng các tham số cuối cùng là int của chúng tôi n, vì vậy đó là chiều dài của mảng của chúng tôi.
>> Trong các cuộc gọi đệ quy để tìm kiếm, chúng tôi bây giờ nói rằng chiều dài của
mảng là trung.
Vì vậy, nếu mảng của chúng tôi là các kích thước 20 và chúng tôi tìm kiếm ở chỉ số 10, từ giữa là
20 chia cho 2, có nghĩa là chúng tôi đi qua 10 như mới
chiều dài của mảng của chúng tôi.
Hãy nhớ rằng khi bạn có một mảng chiều dài 10, có nghĩa là hợp lệ
yếu tố nằm trong các chỉ số từ 0 đến 9.
Vì vậy, đây là chính xác những gì chúng tôi muốn chỉ định mảng cập nhật của chúng tôi - bên trái
mảng từ các yếu tố trung.
>> Vì vậy, nhìn bên phải là một chút khó khăn hơn.
Bây giờ đầu tiên, chúng ta hãy xem xét độ dài của mảng bên phải của
yếu tố trung.
Vì vậy, nếu mảng của chúng tôi là kích thước n, thì mảng mới sẽ có kích thước n trừ đi
trừ giữa 1.
Vì vậy, chúng ta hãy nghĩ n trừ đi giữa.
>> Một lần nữa, nếu mảng đều có cỡ 20 và chúng tôi chia cho 2 để có được giữa,
nên giữa là 10, sau đó trừ đi n trung sẽ cung cấp cho chúng tôi 10, vì vậy 10
các yếu tố bên phải của trung.
Nhưng chúng tôi cũng có trừ này 1, vì chúng ta không muốn
bao gồm giữa chính nó.
Vì vậy, trừ n trung trừ đi 1 cho chúng ta tổng số của các yếu tố bên phải
của chỉ số trung trong mảng.
>> Bây giờ ở đây, hãy nhớ rằng giữa tham số là mảng giá trị.
Vì vậy, ở đây, chúng tôi đang đi qua một cập nhật các giá trị mảng.
Này các giá trị cộng thêm 1 trung là thực sự nói đệ quy gọi
tìm kiếm, đi qua trong một mảng mới, nơi mà mảng mới bắt đầu ở giữa
cộng với một trong những mảng giá trị ban đầu của chúng tôi.
>> Một cú pháp thay thế cho rằng, bây giờ mà bạn đã bắt đầu nhìn thấy con trỏ, là
giá trị ký hiệu cộng với trung 1.
Vì vậy, lấy địa chỉ của trung cộng với một yếu tố của giá trị.
>> Bây giờ, nếu bạn không thoải mái sửa đổi một mảng như thế, bạn
cũng có thể thực hiện điều này bằng cách sử dụng một chức năng trợ giúp đệ quy, nơi
mà có chức năng trợ giúp nhiều đối số.
Vì vậy, thay vì dùng chỉ giá trị, mảng, và kích thước của mảng,
các chức năng trợ giúp có thể mất nhiều hơn lập luận, trong đó có chỉ số thấp hơn
mà bạn sẽ quan tâm trong mảng và chỉ số trên mà bạn quan tâm
về mảng.
>> Và do đó việc theo dõi của cả hai thấp hơn chỉ số và chỉ số trên, bạn không
cần phải bao giờ thay đổi giá trị ban đầu mảng.
Bạn chỉ có thể tiếp tục sử dụng các mảng giá trị.
Nhưng ở đây, nhận thấy chúng tôi không cần một người trợ giúp chức năng miễn là chúng tôi
sẵn sàng thay đổi bản gốc giá trị mảng.
Chúng tôi sẵn sàng để vượt qua trong một cập nhật các giá trị.
>> Bây giờ, chúng ta không thể tìm kiếm nhị phân trên một mảng đó là phân loại.
Vì vậy, chúng ta hãy sắp xếp này ra.
Bây giờ, nhận thấy loại đó là quá khứ hai thông số int giá trị, đó là
mảng mà chúng ta đang phân loại, và int n, đó là chiều dài của mảng mà
chúng tôi đang phân loại.
Vì vậy, ở đây chúng tôi muốn thực hiện một thuật toán sắp xếp
đó là o n bình phương.
Bạn có thể chọn bong bóng sắp xếp, lựa chọn sắp xếp, hoặc sắp xếp chèn, hoặc
một số loại khác mà chúng tôi có không thấy trong lớp.
Nhưng ở đây, chúng ta sẽ sử dụng lựa chọn sắp xếp.
>> Vì vậy, chúng ta sẽ lặp trên toàn bộ mảng.
Vâng, ở đây chúng ta thấy rằng chúng ta đang lặp lại từ 0 đến n trừ đi 1.
Tại sao không phải tất cả các con đường lên đến n?
Vâng, nếu chúng tôi đã sắp xếp đầu tiên n trừ đi 1 yếu tố, sau đó các
yếu tố cuối cùng những gì đã phải trong địa điểm chính xác, vì vậy sắp xếp hơn
toàn bộ mảng.
>> Bây giờ, nhớ làm thế nào lựa chọn loại hoạt động.
Chúng ta sẽ đi qua toàn bộ mảng tìm kiếm các giá trị tối thiểu trong
mảng và cây gậy lúc đầu.
Sau đó chúng ta sẽ đi qua toàn bộ mảng một lần nữa tìm kiếm thứ hai
phần tử nhỏ nhất, và cây gậy ở vị trí thứ hai trong
mảng, và như vậy.
Vì vậy, đó là những gì đang thực hiện.
>> Ở đây, chúng ta đang thấy rằng chúng tôi thiết lập tối thiểu hiện hành
giá trị cho chỉ số thứ i.
Vì vậy, trên phiên đầu tiên, chúng ta sẽ xem xét các giá trị tối thiểu là
sự bắt đầu của mảng của chúng tôi.
Sau đó, chúng ta sẽ lặp qua còn lại của mảng, kiểm tra để
xem nếu có bất kỳ yếu tố nhỏ hơn một trong đó chúng tôi hiện đang
xem xét mức tối thiểu.
>> Vì vậy, ở đây, giá trị j cộng với một - đó là ít hơn những gì chúng tôi đang có
xem xét mức tối thiểu.
Sau đó chúng ta sẽ cập nhật những gì chúng tôi nghĩ là tối thiểu để
chỉ số j cộng với 1.
Vì vậy, làm điều đó trên toàn bộ mảng, và sau này cho vòng lặp, tối thiểu
nên là yếu tố tối thiểu từ vị trí thứ i trong mảng.
>> Một khi chúng ta có điều đó, chúng ta có thể trao đổi các giá trị tối thiểu vào vị trí thứ i
trong mảng.
Vì vậy, đây chỉ là một trao đổi tiêu chuẩn.
Chúng tôi lưu trữ trong một giá trị tạm thời - giá trị thứ i trong mảng -
đưa vào giá trị thứ i trong mảng các giá trị tối thiểu mà thuộc về ở đó,
và sau đó lưu trữ trở lại nơi giá trị tối thiểu hiện hành được sử dụng là
giá trị thứ i trong mảng, vì vậy rằng chúng tôi đã không mất nó.
>> Vì vậy, mà vẫn tiếp tục trên phiên bản kế tiếp.
Chúng tôi sẽ bắt đầu tìm kiếm thứ hai giá trị tối thiểu và chèn đó vào
vị trí thứ hai.
Trên lặp thứ ba, chúng tôi sẽ tìm kiếm giá trị nhỏ nhất thứ ba và chèn
đó vào vị trí thứ ba, và vì vậy cho đến khi chúng tôi có một mảng được sắp xếp.
Tên tôi là Rob, và điều này là lựa chọn sắp xếp.