Cấu trúc và thuật toán dữ liệu hàng đầu trong Java mà bạn cần biết

Blog này về Cấu trúc dữ liệu và Thuật toán trong Java sẽ giúp bạn hiểu tất cả các cấu trúc và thuật toán dữ liệu chính trong Java.

Nếu tôi phải chọn một chủ đề quan trọng nhất trong phát triển phần mềm, đó sẽ là cấu trúc dữ liệu và thuật toán. Bạn có thể coi nó như một công cụ cơ bản có sẵn cho mọi lập trình viên máy tính. Trong khi lập trình, chúng tôi sử dụng cấu trúc dữ liệu để lưu trữ và sắp xếp dữ liệu, và thuật toán để thao tác dữ liệu trong các cấu trúc đó. Bài viết này bao gồm đánh giá chi tiết về tất cả các cấu trúc dữ liệu và thuật toán phổ biến trong để cho phép người đọc được trang bị tốt.

Dưới đây là các chủ đề được thảo luận trong bài viết này:





Cấu trúc dữ liệu trong Java

Cấu trúc dữ liệu là một cách lưu trữ và tổ chức dữ liệu trong máy tính để nó có thể được sử dụng một cách hiệu quả. Nó cung cấp một phương tiện để quản lý một lượng lớn dữ liệu một cách hiệu quả. Và cấu trúc dữ liệu hiệu quả là chìa khóa để thiết kế các thuật toán hiệu quả.

Trongbài viết ‘Cấu trúc dữ liệu và thuật toán trong Java’ này, chúng tôi sẽ đề cập đến các cấu trúc dữ liệu cơ bản như:



Hãy kiểm tra từng người trong số họ.

Cấu trúc dữ liệu tuyến tính trong Java

Cấu trúc dữ liệu tuyến tính trong là những phần tử có các phần tử được sắp xếp theo thứ tự và được sắp xếp theo cách sao cho: chỉ có một yếu tố đầu tiên và chỉ có một yếu tố tiếp theo , chỉ có một yếu tố cuối cùng và chỉ có một phần tử trước , trong khi tất cả các phần tử khác có kế tiếp và một Trước thành phần.

Mảng

An mảng là một cấu trúc dữ liệu tuyến tínhđại diện cho một nhóm các phần tử tương tự, được truy cập bằng chỉ mục. Kích thước của một mảng phải được cung cấp trước khi lưu trữ dữ liệu. Dưới đây là danh sách các thuộc tính của một mảng:



  • Mỗi phần tử trong một mảng có cùng kiểu dữ liệu và có cùng kích thước
  • Các phần tử của mảng được lưu trữ tại các vị trí bộ nhớ liền kề với phần tử đầu tiên bắt đầu ở vị trí bộ nhớ nhỏ nhất
  • Các phần tử của mảng có thể được truy cập ngẫu nhiên
  • Cấu trúc dữ liệu mảng không hoàn toàn động

Mảng - Edureka

Ví dụ , chúng tôi có thể muốn một trò chơi điện tử theo dõi mười điểm hàng đầu cho trò chơi đó. Thay vì sử dụng mười khác nhau biến đối với nhiệm vụ này, chúng tôi có thể sử dụng một tên duy nhất cho toàn bộ nhóm và sử dụng số chỉ mục để chỉ điểm cao trong nhóm đó.

Danh sách liên kết

ĐẾN là một cấu trúc dữ liệu tuyến tính với tập hợp nhiều nút, trong đó ePhần tử ach lưu trữ dữ liệu của chính nó và một con trỏ đến vị trí của phần tử tiếp theo. Liên kết cuối cùng trong danh sách được liên kết trỏ đến null, cho biết phần cuối của chuỗi. Một phần tử trong danh sách liên kết được gọi là nút . Nút đầu tiên được gọi là cái đầu .Nút cuối cùng được gọi làcác đuôi .

Các loại danh sách được liên kết

cách sử dụng phương thức phân tách trong java

Danh sách liên kết đơn (đơn hướng)

Danh sách được liên kết kép (Hai chiều)

Danh sách liên kết hình tròn

Đây là một ví dụ đơn giản: Hãy tưởng tượng một danh sách được liên kết giống như một chuỗi các tập giấy được liên kết với nhau. Bạn có thể dễ dàng thêm một chiếc kẹp giấy khác vào đầu hoặc cuối. Việc chèn một cái vào giữa thậm chí còn nhanh chóng. Tất cả những gì bạn phải làm là chỉ cần ngắt dây xích ở giữa, thêm chiếc kẹp giấy mới, sau đó kết nối lại nửa còn lại. Một danh sách liên kết cũng tương tự.

Ngăn xếp

Cây rơm, một cấu trúc dữ liệu trừu tượng, là một tập hợp của các đối tượng được chèn và loại bỏ theo cuối cùng vào trước (LIFO) nguyên tắc. Các đối tượng có thể được chèn vào một ngăn xếp bất kỳ lúc nào, nhưng chỉ đối tượng được chèn gần đây nhất (tức là “cuối cùng”) mới có thể bị xóa bất kỳ lúc nào.Liệt kê bên dưới là các thuộc tính của ngăn xếp:

  • Nó là một danh sách orderd trong đóviệc chèn và xóa chỉ có thể được thực hiện ở một đầu được gọi là hàng đầu
  • Cấu trúc dữ liệu đệ quy với một con trỏ đến phần tử trên cùng của nó
  • Theo dõi cuối cùng vào trước (LIFO) nguyên tắc
  • Hỗ trợ hai phương pháp cơ bản nhất
    • push (e): Chèn phần tử e, lên đầu ngăn xếp
    • pop (): Loại bỏ và trả lại phần tử trên cùng trên ngăn xếp

Các ví dụ thực tế về ngăn xếp bao gồm khi đảo ngược một từ,để kiểm tra tính đúng đắn của dấu ngoặc đơnsự nối tiếp,triển khai chức năng trở lại trong trình duyệt và nhiều hơn nữa.

Hàng đợi

cũng là một kiểu cấu trúc dữ liệu trừu tượng khác. Không giống như một ngăn xếp, hàng đợi là một tập hợp các đối tượng được chèn và loại bỏ theo nhập trước - xuất trước (FIFO) nguyên tắc. Có nghĩa là, các phần tử có thể được chèn vào bất kỳ thời điểm nào, nhưng chỉ phần tử nằm trong hàng đợi lâu nhất mới có thể bị xóa bất kỳ lúc nào.Liệt kê dưới đây là các thuộc tính của hàng đợi:

  • Thường được gọi là đến trước về trước danh sách
  • Hỗ trợ hai phương pháp cơ bản nhất
    • enqueue (e): Chèn phần tử e, tại phần phía sau của hàng đợi
    • dequeue (): Loại bỏ và trả lại phần tử từ trước mặt của hàng đợi

Hàng đợi được sử dụng trongtruyền dữ liệu không đồng bộ giữa hai quy trình, lập lịch CPU, lập lịch đĩa và các tình huống khác trong đó tài nguyên được chia sẻ giữa nhiều người dùng và được phục vụ trên cơ sở máy chủ đến trước. Tiếp theo trong bài viết ‘Cấu trúc dữ liệu và thuật toán trong Java’ này, chúng ta có cấu trúc dữ liệu phân cấp.

Cấu trúc dữ liệu phân cấp trong Java

Cây nhị phân

Cây nhị phân là mộtcấu trúc dữ liệu cây phân cấp trong đó mỗi nút có nhiều nhất hai nút con , được gọi là con tráiđúng đứa trẻ . Mỗi cây nhị phân có các nhóm nút sau:

  • Nút gốc: Nó là nút trên cùng và thường được gọi là nút chínhbởi vì tất cả các nút khác có thể được truy cập từ gốc
  • Cây phụ bên trái, cũng là cây nhị phân
  • Cây con bên phải, cũng là cây nhị phân

Dưới đây là các thuộc tính của cây nhị phân:

  • Cây nhị phân có thể được duyệt theo hai cách:
    • Độ sâu Truyền tải đầu tiên : Theo thứ tự (Left-Root-Right), Preorder (Root-Left-Right) và Postorder (Left-Right-Root)
    • Breadth First Traversal : Truyền đơn hàng cấp độ
  • Độ phức tạp về thời gian của dịch chuyển cây: O (n)
  • Số nút tối đa ở mức ‘l’ = 2l-1.

Các ứng dụng của cây nhị phân bao gồm:

  • Được sử dụng trong nhiều ứng dụng tìm kiếm nơi dữ liệu liên tục vào / ra
  • Là một quy trình làm việc để tổng hợp hình ảnh kỹ thuật số cho hiệu ứng hình ảnh
  • Được sử dụng trong hầu hết mọi bộ định tuyến băng thông cao để lưu trữ bảng bộ định tuyến
  • Cũng được sử dụng trong mạng không dây và phân bổ bộ nhớ
  • Được sử dụng trong các thuật toán nén và nhiều hơn nữa

Binary Heap

Binary Heap là mộtCây nhị phân, câu trả lời cho thuộc tính đống. Nói một cách đơn giản nólà một biến thể của cây nhị phân với các thuộc tính sau:

  • Heap là một cây nhị phân hoàn chỉnh: Một cái cây được cho là hoàn chỉnh nếu tất cả các cấp của nó, ngoại trừ có thể là sâu nhất, đều hoàn chỉnh. Ttài sản của anh ta về Binary Heap làm cho nó phù hợp để được lưu trữ trong một .
  • Theo dõi thuộc tính đống: Một đống nhị phân là một Min-Heap hoặc một Max-Heap .
    • Min Binary Heap: Fhoặc mọi nút trong một đống, giá trị của nút là nhỏ hơn hoặc bằng giá trị của trẻ em
    • Khối nhị phân tối đa: Fhoặc mọi nút trong một đống, giá trị của nút là lớn hơn hoặc bằng giá trị của trẻ em

Các ứng dụng phổ biến của đống nhị phân bao gồmtriển khai hàng đợi ưu tiên hiệu quả, hiệu quả tìm k phần tử nhỏ nhất (hoặc lớn nhất) trong một mảng và nhiều phần tử khác.

Bảng băm

Hãy tưởng tượng rằng bạn có một vật và bạn muốn gán một khóa cho nó để giúp việc tìm kiếm trở nên rất dễ dàng. Để lưu trữ cặp khóa / giá trị đó, bạn có thể sử dụng một mảng đơn giản như cấu trúc dữ liệu trong đó các khóa (số nguyên) có thể được sử dụng trực tiếp như một chỉ mục để lưu trữ các giá trị dữ liệu. Tuy nhiên, trong trường hợp các khóa quá lớn và không thể được sử dụng trực tiếp làm chỉ mục, một kỹ thuật gọi là băm được sử dụng.

Khi băm, các khóa lớn được chuyển đổi thành các khóa nhỏ bằng cách sử dụng hàm băm . Các giá trị sau đó được lưu trữ trong một cấu trúc dữ liệu được gọi làđến bảng băm. Bảng băm là một cấu trúc dữ liệu thực hiện một ADT từ điển, một cấu trúc có thể ánh xạ các khóa duy nhất đến các giá trị.

Nói chung, bảng băm có hai thành phần chính:

  1. Mảng nhóm: Mảng nhóm cho một bảng băm là một mảng A có kích thước N, trong đó mỗi ô của A được coi như một “thùng”, tức là một tập hợp các cặp khóa-giá trị. Số nguyên N xác định dung lượng của mảng.
  2. Hàm băm: Nó là bất kỳ hàm nào ánh xạ mỗi khóa k trong bản đồ của chúng ta thành một số nguyên trong phạm vi [0, N & trừ 1], trong đó N là dung lượng của mảng thùng cho bảng này.

Khi chúng ta đặt các đối tượng vào một bảng băm, có thể các đối tượng khác nhau có thể có cùng một mã băm. Đây được gọi là va chạm . Để đối phó với va chạm, có các kỹ thuật như chuỗi và định địa chỉ mở.

Vì vậy, đây là một số cấu trúc dữ liệu cơ bản và được sử dụng thường xuyên nhất trong Java. Bây giờ bạn đã biết về từng điều này, bạn có thể bắt đầu triển khai chúng trong . Với điều này, chúng tôi đã hoàn thành phần đầu tiên của 'bài viết' Cấu trúc dữ liệu và thuật toán trong Java 'này. Trong phần tiếp theo, chúng ta sẽ tìm hiểu vềcác thuật toán cơ bản và cách sử dụng chúng trong các ứng dụng thực tế như sắp xếp và tìm kiếm, chia và chinh phục, thuật toán tham lam, lập trình động.

Các thuật toán trong Java

Trong lịch sử được sử dụng như một công cụ để giải các phép tính toán học phức tạp, các thuật toán có mối liên hệ sâu sắc với khoa học máy tính và đặc biệt là với cấu trúc dữ liệu. Một thuật toán là một chuỗi các hướng dẫn mô tả cách giải quyết một vấn đề cụ thể trong một khoảng thời gian hữu hạn. Chúng được biểu diễn theo hai cách:

  • Lưu đồ - Nó là mộttrình bày trực quan luồng điều khiển của thuật toán
  • Mã giả - Nólà một biểu diễn dạng văn bản của một thuật toán gần đúng với mã nguồn cuối cùng

Ghi chú: Hiệu suất của thuật toán được đo lường dựa trên độ phức tạp về thời gian và độ phức tạp về không gian. Hầu hết, độ phức tạp của bất kỳ thuật toán nào đều phụ thuộc vào vấn đề và chính thuật toán đó.

Hãy cùng khám phá hai loại thuật toán chính trong Java, đó là:

Sắp xếp các thuật toán trong Java

Thuật toán sắp xếp là thuật toán xếp các phần tử của danh sách theo một thứ tự nhất định. Các thứ tự được sử dụng phổ biến nhất là thứ tự số và thứ tự từ vựng. Trong bài viết 'Cấu trúc dữ liệu và thuật toán' này, chúng ta hãy khám phá một vài thuật toán sắp xếp.

Sắp xếp bong bóng trong Java

hashset trong java là gì

Bubble Sort, thường được gọi là sắp xếp chìm, là thuật toán sắp xếp đơn giản nhất. Nó lặp lại bước qua danh sách được sắp xếp, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự.Sắp xếp bong bóng có tên như vậy vì nó lọc ra các phần tử ở trên cùng của mảng, giống như bong bóng nổi trên mặt nước.

Đây làmã giả đại diện cho Thuật toán sắp xếp bong bóng (ngữ cảnh sắp xếp tăng dần).

a [] là một mảng có kích thước N bắt đầu BubbleSort (a []) khai báo số nguyên i, j cho i = 0 đến N - 1 cho j = 0 đến N - i - 1 nếu a [j]> a [j + 1 ] sau đó hoán đổi một [j], một [j + 1] kết thúc nếu kết thúc để trả về một BubbleSort kết thúc

Mã này sắp xếp một mảng một chiều gồm N mục dữ liệu theo thứ tự tăng dần. Một vòng lặp bên ngoài làm cho N-1 đi qua mảng. Mỗi lần vượt qua sử dụng một vòng lặp bên trong để trao đổi các mục dữ liệu sao cho mục dữ liệu nhỏ nhất tiếp theo 'bong bóng' về phía đầu mảng. Nhưng vấn đề là thuật toán cần một lần chuyển toàn bộ mà không có bất kỳ sự hoán đổi nào để biết rằng danh sách đã được sắp xếp.

Độ phức tạp của trường hợp xấu nhất và trung bình: O (n * n). Trường hợp xấu nhất xảy ra khi một mảng được sắp xếp ngược lại.

Độ phức tạp về thời gian của trường hợp tốt nhất Trên). Trường hợp tốt nhất xảy ra khi một mảng đã được sắp xếp.

Sắp xếp lựa chọn trong Java

Sắp xếp lựa chọn là sự kết hợp của cả tìm kiếm và sắp xếp. Thuật toán sắp xếp một mảng bằng cách liên tục tìm phần tử tối thiểu (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó vào một vị trí thích hợp trong mảng.

Đây là mã giả đại diện cho Thuật toán sắp xếp lựa chọn (ngữ cảnh sắp xếp tăng dần).

a [] là một mảng có kích thước N begin SelectionSort (a []) for i = 0 to n - 1 / * đặt phần tử hiện tại là nhỏ nhất * / min = i / * tìm phần tử nhỏ nhất * / for j = i + 1 đến n nếu danh sách [j]

Như bạn có thể hiểu từ mã, số lần sắp xếp đi qua mảng nhỏ hơn một lần so với số mục trong mảng. Vòng lặp bên trong tìm giá trị nhỏ nhất tiếp theo và vòng lặp bên ngoài đặt giá trị đó vào vị trí thích hợp của nó. Việc sắp xếp lựa chọn không bao giờ tạo ra nhiều hơn O (n) lần hoán đổi và có thể hữu ích khi việc ghi bộ nhớ là một hoạt động tốn kém.

Thời gian phức tạp: Trên2) vì có hai vòng lặp lồng nhau.

Không gian phụ trợ: Hoặc (1).

Sắp xếp chèn trong Java

Insertion Sort là một thuật toán sắp xếp đơn giản lặp lại qua danh sách bằng cách sử dụng một phần tử đầu vào tại một thời điểm và xây dựng mảng được sắp xếp cuối cùng. Nó rất đơn giản và hiệu quả hơn trên các tập dữ liệu nhỏ hơn. Đó là kỹ thuật sắp xếp ổn định và tại chỗ.

Đây là mã giả đại diện cho Thuật toán sắp xếp chèn (ngữ cảnh sắp xếp tăng dần).

a [] là một mảng có kích thước N begin InsertionSort (a []) for i = 1 to N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 end trong khi a [j + 1] = key end cho end InsertionSort

Như bạn có thể hiểu từ mã, thuật toán sắp xếp chènxóa một phần tử khỏi dữ liệu đầu vào, tìm vị trí của phần tử đó trong danh sách đã sắp xếp và chèn phần tử đó vào đó. Nó lặp lại cho đến khi không có phần tử đầu vào nào vẫn chưa được sắp xếp.

Trường hợp tốt nhất: Trường hợp tốt nhất là khi đầu vào là một mảng đã được sắp xếp. Trong trường hợp này, sắp xếp chèn có thời gian chạy tuyến tính (tức là & Theta (n)).

Trường hợp xấu nhất: Đầu vào trường hợp xấu nhất đơn giản nhất là một mảng được sắp xếp theo thứ tự ngược lại.

QuickSort trong Java

Thuật toán Quicksort là một thuật toán sắp xếp nhanh, đệ quy, không ổn định, hoạt động theo nguyên tắc chia và trị. Nó chọn một phần tử làm trục và phân vùng mảng đã cho xung quanh trục đã chọn đó.

Các bước thực hiện Sắp xếp nhanh:

  1. Chọn một 'điểm xoay' phù hợp.
  2. Chia danh sách thành hai danh sáchdựa trên yếu tố trục này. Mọi phần tử nhỏ hơn phần tử pivot được đặt trong danh sách bên trái và mọi phần tử lớn hơn được đặt trong danh sách bên phải. Nếu một phần tử bằng với phần tử pivot thì nó có thể nằm trong bất kỳ danh sách nào. Đây được gọi là hoạt động phân vùng.
  3. Sắp xếp đệ quy từng danh sách nhỏ hơn.

Đây là mã giả đại diện cho Thuật toán Quicksort.

QuickSort (A dưới dạng mảng, thấp là int, cao là int) {if (thấp

Trong mã giả trên, vách ngăn() chức năng thực hiện hoạt động phân vùng và Sắp xếp nhanh chóng() hàm liên tục gọi hàm phân vùng cho mỗi danh sách nhỏ hơn được tạo. Độ phức tạp của quicksort trong trường hợp trung bình là & Theta (n log (n)) và trong trường hợp xấu nhất là & Theta (n2).

Hợp nhất Sắp xếp trong Java

Mergesort là một thuật toán sắp xếp nhanh, đệ quy, ổn định, cũng hoạt động theo nguyên tắc chia và chinh phục. Tương tự như quicksort, sắp xếp hợp nhất chia danh sách các phần tử thành hai danh sách. Các danh sách này được sắp xếp độc lập và sau đó được kết hợp. Trong quá trình kết hợp danh sách, các phần tử được chèn (hoặc hợp nhất) vào đúng vị trí trong danh sách.

Đây là mã giả đại diện cho Thuật toán Sắp xếp Hợp nhất.

thủ tục MergeSort (a as array) if (n == 1) return a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergeort (l1) l2 = mergesort (l2) return merge (l1, l2) end process procedure merge (a as array, b as array) var c as array while (a and b has element) if ( a [0]> b [0]) thêm b [0] vào cuối c xóa b [0] khỏi b khác thêm a [0] vào cuối c xóa a [0] khỏi cuối nếu kết thúc while (a có phần tử) thêm a [0] vào cuối c xóa a [0] khỏi cuối trong khi (b có phần tử) thêm b [0] vào cuối c loại bỏ b [0] khỏi b kết thúc trong khi trả về c kết thúc thủ tục

mergeort () hàm chia danh sách thành hai, gọi mergeort () trên các danh sách này riêng biệt và sau đó kết hợp chúng bằng cách gửi chúng dưới dạng các tham số cho hàm merge ().Thuật toán có độ phức tạp là O (n log (n)) và có nhiều ứng dụng.

Sắp xếp đống trong Java

Heapsort là một thuật toán sắp xếp dựa trên so sánhCấu trúc dữ liệu Heap nhị phân. Bạn có thể coi nó là loại lựa chọn phiên bản f được cải tiến, trong đónó chia đầu vào của nó thành một vùng đã được sắp xếp và một vùng chưa được sắp xếp, và nó sẽ thu nhỏ lại một cách lặp đi lặp lại vùng chưa được sắp xếp bằng cách trích xuất phần tử lớn nhất và chuyển phần tử đó đến vùng đã sắp xếp.

Các bước thực hiện Quicksort (theo thứ tự tăng dần):

  1. Xây dựng một đống tối đa với mảng sắp xếp
  2. Tại poin nàyt, mục lớn nhất được lưu trữ ở gốc của đống. Thay thế nó bằng mục cuối cùng của đống và giảm kích thước của đống đi 1. Cuối cùng, chất đống gốc cây
  3. Lặp lại các bước trên cho đến khi kích thước của đống lớn hơn 1

Đây là mã giả đại diện cho Thuật toán Sắp xếp Heap.

Heapsort (a dưới dạng mảng) for (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) large = i // Khởi tạo lớn nhất dưới dạng root int l eft = 2 * i + 1 // left = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 if (left a [lớn nhất]) lớn nhất = trái nếu (phải a [lớn nhất]) lớn nhất = phải nếu (lớn nhất! = I) swap ( a [i], A [lớn nhất]) Heapify (a, n, lớn nhất) end heapify

Ngoài những thuật toán này, còn có các thuật toán sắp xếp khác không được biết đến nhiều như Introsort, Counting Sort, v.v. Chuyển sang tập hợp thuật toán tiếp theo trong bài viết ‘Cấu trúc dữ liệu và thuật toán’ này, hãy cùng khám phá các thuật toán tìm kiếm.

Tìm kiếm thuật toán trong Java

Tìm kiếm là một trong những hành động phổ biến nhất và thường xuyên được thực hiện trong các ứng dụng kinh doanh thông thường. Thuật toán tìm kiếm là các thuật toán để tìm một mục với các thuộc tính được chỉ định trong một tập hợp các mục. Hãy khám phá hai trong số các thuật toán tìm kiếm được sử dụng phổ biến nhất.

Thuật toán tìm kiếm tuyến tính trong Java

Tìm kiếm tuyến tính hoặc tìm kiếm tuần tự là thuật toán tìm kiếm đơn giản nhất. Nó liên quan đến việc tìm kiếm tuần tự một phần tử trong cấu trúc dữ liệu đã cho cho đến khi phần tử được tìm thấy hoặc đến phần cuối của cấu trúc. Nếu phần tử được tìm thấy, thì vị trí của mục được trả về, nếu không, thuật toán trả về NULL.

Đây là mã giả đại diện cho Tìm kiếm tuyến tính trong Java:

thủ tục linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search

Nó là mộtthuật toán vét cạn.Mặc dù nó chắc chắn là đơn giản nhất, nhưng nó chắc chắn không phải là phổ biến nhất do tính kém hiệu quả của nó. Độ phức tạp về thời gian của tìm kiếm tuyến tính là TRÊN) .

Thuật toán tìm kiếm nhị phân trong Java

Tìm kiếm nhị phân, còn được gọi là tìm kiếm logarit, 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. Nó chia bộ sưu tập đầu vào thành các nửa bằng nhau và mục được so sánh với phần tử ở giữa của danh sách. Nếu phần tử được tìm thấy, việc tìm kiếm sẽ kết thúc ở đó. Ngoài ra, chúng tôi tiếp tục tìm kiếm phần tử bằng cách chia và chọn phân vùng thích hợp của mảng, dựa trên xem phần tử đích nhỏ hơn hay lớn hơn phần tử ở giữa.

Đây là mã giả đại diện cho Tìm kiếm nhị phân trong Java:

Thủ tục binary_search một mảng đã được sắp xếp có kích thước n của mảng x giá trị được tìm kiếm LowerBound = 1 upperBound = n trong khi x không được tìm thấy nếu upperBound

Tìm kiếm kết thúc khi upperBound (con trỏ của chúng ta) đi qua LowerBound (phần tử cuối cùng), điều này ngụ ý rằng chúng ta đã tìm kiếm toàn bộ mảng và phần tử không có mặt.Đây là thuật toán tìm kiếm được sử dụng phổ biến nhất chủ yếu do thời gian tìm kiếm nhanh chóng. Độ phức tạp về thời gian của tìm kiếm nhị phân là TRÊN) đó là một cải tiến rõ rệt về TRÊN) độ phức tạp về thời gian của Tìm kiếm tuyến tính.

sử dụng không gian tên c ++

Phần này sẽ đưa chúng ta đến phần cuối của bài viết ‘Cấu trúc dữ liệu và thuật toán trong Java’. Tôi đã đề cập đến một trong những chủ đề cơ bản và quan trọng nhất của Java.Hy vọng bạn đã rõ ràng với tất cả những gì đã được chia sẻ với bạn trong bài viết này.

Đảm bảo rằng bạn luyện tập nhiều nhất có thể và hoàn nguyên trải nghiệm của mình.

Kiểm tra của Edureka, một công ty học trực tuyến đáng tin cậy với mạng lưới hơn 250.000 người học hài lòng trải dài trên toàn cầu. Chúng tôi ở đây để giúp bạn từng bước trong hành trình của bạn, để trở thành một người ngoài câu hỏi phỏng vấn java này, chúng tôi còn đưa ra một chương trình giảng dạy được thiết kế cho sinh viên và chuyên gia muốn trở thành một Nhà phát triển Java.

Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần nhận xét của 'Cấu trúc dữ liệu và thuật toán trong Java' và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.