Thuật toán “khét tiếng”: Tìm kiếm nhị phân trong Python

Ảnh của Mark Tegethoff trên Unsplash

Giới thiệu

Hãy khởi đầu đề tài lúc này với hai thắc mắc.

Ấn tượng trước tiên của các bạn về việc học thuật toán là gì?

Thuật toán là gì?

Ngày nay, có hàng đống từ phổ biến nổi tiếng như “bit”, “Intelligence”, “Artificial Intelligence”, “learning”, “Supervised Learning” & “thuật toán” đang ở trên kệ vị trí thứ nhất.

Nhưng ít người hiểu những từ này thực sự đại diện cho điều gì, càng ít nói lên cách chúng hoạt động.

“Cái gì vậy?

Nó làm gì?”

Bạn đã hỏi.

So với tôi, thuật toán là một tiến trình tất cả chúng ta mong muốn laptop giải quyết thông tin như vậy nào, cái gì đến trước cái sau.

Này là nó.

Dễ dàng vậy thôi.

Tôi đã giải thích cặn kẽ về đề tài mà các cuộc phỏng vấn Khoa học Dữ liệu đã trở nên theo hướng lập trình hơn & theo định hướng CS trong hai bài đăng ( Python & FAANG ). Trong bài đăng lúc này, tôi sẽ giới thiệu cho các bạn những điều căn bản & quan niệm của Tìm kiếm nhị phân & đáp án một số thắc mắc phỏng vấn thực tiễn do FAANG đề ra. Tìm kiếm nhị phân chắc cú là một trong những thuật toán được thí nghiệm nhiều nhất, còn nếu như không mong muốn nói là duy nhất, dễ chớp lấy một cách đáng bất ngờ.

Tìm kiếm nhị phân: Cái gì & như vậy nào

Về mặt chính thức, nó được khái niệm là “một thuật toán tìm kiếm tìm vị trí của giá trị đích trong một mảng được sắp xếp” & so sánh giá trị đích với phần tử ở giữa, kiểm soát xem chúng có tương tự hay không. Nếu chúng không bằng nhau, hãy chuyển sang khoảng kế tiếp để so sánh (phỏng theo Wiki ).

Không chính thức, khái niệm trực quan của tôi là chia đôi phạm vi tìm kiếm & hỏi laptop xem khoảng đã chọn có chứa giá trị không: nếu khoảng bé hơn giá trị mục tiêu, hãy di chuyển lên không gian tìm kiếm & tìm kiếm lại; còn nếu như không, hãy di chuyển xuống.

Một trò chơi đoán theo thứ tự. Nó được gọi là “Số của tôi là gì?” Về căn bản, tôi chọn một số từ 1 đến 100, & công việc của các bạn là tìm số bằng cách đặt thắc mắc cho tôi.

Có hai phương pháp để tìm số: không hiệu quả & hiệu quả. Trước tiên, bạn có thể hỏi tôi nếu số là 1; còn nếu như không, hãy kiểm soát các số còn sót lại trong phạm vi cho đến 100. Nếu tôi chọn 100, bạn sẽ phải mất 100 lần mới đúng. Đây được gọi là cách thức Brutal Force, cách thức này hoạt động nhưng không hiệu quả. Bạn sẽ làm gì nếu con số từ 1 đến 1 triệu?

Thứ hai, một cách tiếp cận thông minh & hiệu quả hơn là đặt những thắc mắc như sau:

# 1 Thắc mắc: “Con số của bạn có cao hơn 50 không?”

“Không.”

Chính vì như vậy, số phải từ 1 đến 49! Chúng tôi thậm chí không phải kiểm soát bất kỳ giá trị nào trên 50.

# 2 Thắc mắc: “Con số của bạn có cao hơn 25 không?”

“Đúng.”

Hiện giờ, con số phải rơi vào khoảng từ 26 đến 49! Không cần kiểm soát các số từ 1 đến 25.

Dưới hai thắc mắc, chúng tôi đã thu hẹp phạm vi của con số thực! Bạn sẽ không mất quá nhiều thời gian để có được nó.

Đây là suy nghĩ thuật toán khi chơi trò chơi này. Bất kì danh tiếng cất cánh cao của nó, Binary Search có một cách tiếp cận dễ dàng như thế. Vào cuối ngày, một thuật toán sẽ cho laptop biết cách tiếp cận thông tin. Đây là nguyên tắc số 1 của tôi khi kể tới thuật toán.

Xem Thêm  tràn | Thủ thuật CSS - giá trị tràn mặc định css

Ảnh của Guillermo Ferla trên Unsplash

Triển khai Python

Sau các phép tắc căn bản, đã tới lúc viết một số mã bằng Python. Trong phần này, tôi viết mã trực tiếp qua ba thắc mắc phỏng vấn do các hãng công nghệ đề ra. Có một số phương pháp cho mỗi thắc mắc & tôi giới thiệu cách tiếp cận bằng cách dùng các hàm tích hợp trước khi vận dụng tìm kiếm nhị phân.

Điển hình cho các thử thách viết mã Python, những người phỏng vấn của các bạn cho phép bạn sử dụng bất kỳ cách thức & thư viện tích hợp nào. Miễn là bạn có được kết quả đầu ra như trông mong, bạn có thể đi. Sau đó, họ sẽ đặt thêm các lớp ràng buộc như bạn chẳng thể sử dụng thư viện / gói này hoặc cải tổ năng suất bộ nhớ lưu trữ & vận tốc của các bạn.

Vì mục đích sư phạm, tôi trình bày cả hai cách tiếp cận & vui lòng thực hành cả hai cách tiếp cận trong khi bạn chuẩn bị cho các cuộc phỏng vấn kỹ thuật.

Các thắc mắc sau đã được sắp đặt theo thứ tự không giảm về độ khó . Này là một trò đùa bên trong cho thuật toán tìm kiếm nhị phân. Sau thời điểm học xong bài viết lúc này, bạn sẽ bật cười.

Thắc mắc 1: Sqrt (Ҳ), bởi FAANG

– Cho số nguyên không âm Ҳ, tính & trả về căn bậc hai của Ҳ.
– Vì kiểu trả về là số nguyên nên các chữ số thập phân bị cắt bớt, & chỉ phần nguyên của kết quả được trả về.
– Chẳng hạn, căn bậc hai của 8 là 2,82842, nhưng hàm này chỉ trả về phần nguyên là 2.
https://leetcode.com/problems/sqrtx/

Đi ngang qua nghĩ suy của tôi

Thắc mắc yêu cầu căn bậc hai của một số & chỉ trả về phần nguyên nếu nó không phải là căn bậc hai hoàn hảo. Nó có thể được giải quyết trong vòng hai bước.

# 1. Lấy căn bậc hai của Ҳ;

# 2. Chỉ trả lại phần số nguyên.

Đây là mã Python.

2

Như bạn có thể chấp thuận, điều này sẽ quá đơn giản để được mang vào 1 cuộc phỏng vấn kỹ thuật tại FAANG. Rất có thể, người phỏng vấn của các bạn yêu cầu bạn không sử dụng cách thức có sẵn & vận dụng một số thuật toán.

Bước này, Tìm kiếm nhị phân có lợi. Có ba bước trong thuật toán tìm kiếm nhị phân. Trước khi tất cả chúng ta khởi đầu, hãy bảo đảm rằng mảng đã được sắp đặt, giảm hoặc tăng.

# bước 1. Xác nhận không gian tìm kiếm: trái, phải & giữa

# bước 2. Chúng tôi phỏng đoán lung tung & khởi đầu thuật toán tìm kiếm từ giữa.

# bước 3. Sử dụng câu lệnh “if-else” để kiểm soát giá trị đích & từng phần tử trong không gian tìm kiếm.

3

Điều kiện elif đáng được giải thích. Như đã đề cập ở trên, tìm kiếm nhị phân giống như chơi trò chơi đoán từ 1 đến 100, & bạn có thể đặt một thắc mắc mỗi lần: nó cao hơn hay ít hơn một số. Điều kiện cho biết nếu căn bậc hai bé hơn Ҳ, thì căn bậc hai không đủ lớn, & tất cả chúng ta cần chuyển lên & đoán một số to hơn vào lần sau.

Câu lệnh else điều kiện phải làm gì khi hai điều kiện trên không đáp ứng. Nếu root_squared to hơn số Ҳ của các bạn, laptop sẽ di chuyển xuống không gian tìm kiếm, giống như trò chơi đoán tất cả chúng ta đã chơi trước đây.

Xem Thêm  Hợp nhất danh sách (8 cách) • dữ liệu - cách hợp nhất hai danh sách trong python

Toàn bộ các điều kiện này chấm dứt auto chạy trong vòng lặp while. Cuối cùng, chúng tôi trả về hạn chế trên của không gian tìm kiếm, hay còn được gọi là. đúng .

Như một phương pháp ngăn nắp! Tôi luôn bảo rằng một thuật toán tốt cần có ý nghĩa trực quan, & tìm kiếm nhị phân có rất là nhiều ý nghĩa.

# Thắc mắc 2: Tìm kiếm nhị phân của Amazon, MS, Paypal & Bloomberg

– Cho một số nguyên mảng đã được sắp đặt (theo thứ tự tăng dần) gồm и phần tử & một giá trị đích, hãy viết hàm tìm kiếm mục tiêu theo nums. Nếu mục tiêu tồn tại, thì trả về chỉ mục của nó; còn nếu như không, trả về -1.
https://leetcode.com/problems/binary-search/

Đi ngang qua nghĩ suy của tôi

So với thắc mắc này, lựa chọn cách thức trước tiên của tôi không phải là tìm kiếm nhị phân mà là vận dụng mẹo enumerate () để lặp lại danh mục, được hiển thị như bên dưới:

4

Hiện giờ, hãy sang số & sử dụng tìm kiếm nhị phân.

Biện pháp

4

Cho đến nay, bạn đã hiểu khá rõ về cách thuật toán hoạt động ở dạng căn bản. Đã tới lúc thực hành một vận dụng cầu kỳ hơn của thuật toán.

Ảnh của Greg Rakozy trên Unsplash

# Thắc mắc 3: Kiểm soát xem một số có phải là phần tử đa phần trong một mảng được sắp đặt hay không của Fb

– Cho một số mảng được sắp đặt theo thứ tự không giảm & mục tiêu là số, trả về True nếu & chỉ khi mục tiêu là phần tử đa phần.
– Phần tử đa phần là phần tử hiện ra nhiều hơn И / 2 lần trong một mảng có độ dài И.
https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/

Đi ngang qua nghĩ suy của tôi

Nếu so sánh, đây là một thắc mắc hơi cầu kỳ. Trước tiên của tôi là một cách tiếp cận tuyến tính, rõ ràng là, tìm phần tử đa phần trong một mảng & sau đó quyết định xem giá trị mục tiêu có bằng phần tử đa phần hay không.

Nếu các hàm tích hợp được cho phép, tất cả chúng ta có thể làm như sau:

Result for the 1st check case is:  True
Result for the 2nd check case is:  False

Mọi thứ sẽ trở nên tồi tệ nếu cách thức Counter là khỏi bàn, nhưng chúng tôi không cam chịu.

Tìm kiếm nhị phân có thể tiết kiệm ngày.

Có thể sẽ rất choáng ngợp nếu đây là lần trước tiên bạn học thuật toán, giống như tôi. Chính vì như vậy, tôi tạo nên ba phiên bản của thắc mắc này (độ khó tăng dần). Khi chúng tôi hiểu cách giải đáp hai thắc mắc trước tiên, phiên bản cuối cùng (nguyên bản) sẽ trở nên “dễ giải quyết hơn”.

Phiên bản căn bản 1: Sử dụng tìm kiếm nhị phân để kiểm soát xem giá trị đích có nằm trong một mảng được sắp đặt hay không.

Đơn giản! Đây là một triển khai tiêu chí của thuật toán. Chúng tôi đã đề cập đến vấn đề hậu cần & giải thích cụ thể trong Thắc mắc 1 & 2.

Phiên bản căn bản 2: Sử dụng tìm kiếm nhị phân để tìm lần hiện ra trước tiên & cuối cùng của một phần tử trong một mảng được sắp đặt.

Kế tiếp, hãy thêm gia vị & tìm lần hiện ra trước tiên (ngoài cùng bên trái) của một phần tử & lần hiện ra cuối cùng (ngoài cùng bên phải).

Xem Thêm  Chuyển đổi đối tượng JSON sang mảng JavaScript - js json sang mảng

Việc tìm hàng đầu & cuối cùng của một phần tử là trọng yếu vì nó xác nhận phần tử đa phần là phần tử có độ dài И // 2. Nếu tất cả chúng ta có cơ thể định các chỉ số ngoài cùng bên trái / ngoài cùng bên phải, tất cả chúng ta đang có phương pháp tốt cho phương pháp cuối cùng.

The Leftmost Occurrence is at Position: 2

1. Khi phần tử được chọn bé hơn giá trị đích, tất cả chúng ta cần di chuyển hạn chế bên trái lên trên.

2. Nếu như không, phần tử to hơn hoặc bằng giá trị đích, chúng tôi quyết định phần giữa là hạn chế trên.

The Rightmost Occurrence is at Position: 11

Mã Python hoàn chỉnh có sẵn trên Github của tôi .

# Phiên bản chuyên sâu 3.1: sử dụng tìm kiếm nhị phân để kiểm soát xem mục tiêu có phải là trường hợp đa phần không

True

Các mã trông choáng ngợp nhưng thực sự dễ dàng.

Phần ban đầu được gọi là hàm suport , nó giống như bất kỳ hàm nào khác. Sự độc đáo duy đặc biệt là chúng tôi sẽ sử dụng tính năng được phân phối bởi tính năng suport trong tính năng bên ngoài.

Hàm helper ( từ dòng 8 đến dòng 16 ) tìm địa điểm ngoài cùng bên trái của một phần tử, rất hữu hiệu khi tính toán lần hiện ra trước tiên & cuối cùng của một phần tử trong dòng 24 & 25. Cuối cùng, chúng tôi kiểm soát xem phạm vi, sự độc đáo giữa địa điểm ngoài cùng bên phải & ngoài cùng bên trái, có to hơn И // 2 hay không.

Tôi đã bao gồm một phương pháp cải tạo cho phiên bản 3.1 trên Github của mình .

Xin chúc mừng quãng đường thuật toán của các bạn.

Takeaways

  • Trí óc tăng lên ( Học cách Học ). Bước chân vào những vùng cương vực không xác nhận là điều đáng sợ. Với trí não lớn mạnh, tất cả chúng ta sẽ trở nên giỏi hơn trong những việc tất cả chúng ta làm nếu tất cả chúng ta tiếp tục làm. Tôi đã từng sợ Python & viết mã nói chung. Tôi sợ mình trông sẽ hậu đậu đến mức nào còn nếu như không biết cách viết một vòng lặp for dễ dàng. Với toàn bộ những điều tiêu cực đang diễn ra, thật khó để chăm chú & học hỏi. Viết mã & giải các câu đố khó bằng Python đem lại cho tôi rất là nhiều niềm vui & sự bằng lòng. Python là zen của tôi .
  • Thuật toán . Nó là một ngôn từ khác mà tất cả chúng ta sử dụng để cho laptop biết cách giải quyết thông tin. Bên dưới tiêu đề lạ mắt của nó, một thuật toán rất dễ & dễ hiểu, giống như trò chơi đoán mà chúng tôi đã chơi.
  • Thực hành khiến cho hoàn hảo . 熟能生巧 (Tương tự với tiếng Trung Quốc). Rome không được xây dựng chỉ sau một đêm. Toàn bộ những dấu hiệu thông dụng này cho tất cả chúng ta biết một điều: không gì thay thế được cho sự chuyên cần. Thực hành mỗi ngày, & tất cả chúng ta sẽ giỏi hơn trong việc viết mã, Python, thuật toán & mọi thứ & bất kì thứ gì.

Phần 1: SQL

Phần 2: Đo đạc & Lập trình

Thích đọc cái này?

Hãy tìm tôi trên LinkedIn & Twitter .

không dừng lại ở đó, hãy xem các bài đăng khác của tôi về Trí tuệ nhân tạo & Học máy.

Viết một bình luận