Chào ace, bài xích này bọn họ sẽ tò mò về một trong những thuật toán thu xếp được áp dụng nhiều trong thiết kế và thực tế nhất chính là Binary Search, tiếp sau đây diyxaqaw.com sẽ giới thiệu và share chi tiết(khái niệm, áp dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Binary Search trải qua các phần sau.

Bạn đang xem: Binary search là gì


1. Giới thiệu

Cho một mảng đã bố trí arr <> có n phần tử, hãy viết một hàm để tìm kiếm 1 phần tử x đã mang đến trong arr <>.

Một phương pháp tiếp cận đơn giản dễ dàng là tiến hành tìm kiếm con đường tính(Linear Search), độ tinh vi thời gian của thuật toán bên trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tựa như là thực hiện Tìm tìm nhị phân.

Tìm kiếm nhị phân(Binary Search): kiếm tìm kiếm một mảng được sắp xếp bằng cách chia song khoảng thời gian tìm kiếm nhiều lần. Ban đầu với một khoảng bao gồm toàn cỗ mảng. Nếu giá trị của key tìm kiếm nhỏ dại hơn mục ở khoảng chừng giữa, hãy thu hẹp khoảng chừng đó xuống nửa dưới. Ví như không, hãy thu khiêm tốn nó nghỉ ngơi nửa trên. Tái diễn kiểm tra cho tới khi quý giá được tìm thấy hoặc khoảng thời gian trống.


*

Ý tưởng của search kiếm nhị phân là sử dụng tin tức mà mảng được bố trí và bớt độ tinh vi về thời hạn thành O (Log n).

Về cơ bản chúng ta bỏ sang một nửa số phần tử chỉ sau một lần so sánh.

So sánh x với bộ phận ở giữa.Nếu x khớp với thành phần giữa, chúng ta trả về chỉ số giữa.Ngược lại nếu x bự hơn thành phần giữa, thì x chỉ hoàn toàn có thể nằm trong nửa mảng bé bên đề nghị sau bộ phận giữa. Bởi vì vậy, chúng ta tái diễn cho một nửa bên phải.Ngược lại (x nhỏ tuổi hơn) tái diễn cho nửa bên trái.

2. Code ví dụ trên những ngôn ngữ

2.1 xúc tiến đệ quy với tìm kiếm nhị phân(Binary Search)

C++

// C++ program to lớn implement recursive Binary tìm kiếm #include using namespace std; // A recursive binary tìm kiếm function. It returns // location of x in given array arr is present, // otherwise -1 int binarySearch(int arr<>, int l, int r, int x) if (r >= l) int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); // We reach here when element is not // present in array return -1; int main(void) int arr<> = 2, 3, 4, 10, 40 ; int x = 10; int n = sizeof(arr) / sizeof(arr<0>); int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? cout C

// C program to lớn implement recursive Binary tìm kiếm #include // A recursive binary search function. It returns // location of x in given array arr is present, // otherwise -1 int binarySearch(int arr<>, int l, int r, int x) if (r >= l) int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); // We reach here when element is not // present in array return -1; int main(void) int arr<> = 2, 3, 4, 10, 40 ; int n = sizeof(arr) / sizeof(arr<0>); int x = 10; int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; Java


// Java implementation of recursive Binary search class BinarySearch // Returns index of x if it is present in arr, else return -1 int binarySearch(int arr<>, int l, int r, int x) if (r >= l) int mid = l + (r - l) / 2; // If the element is present at the // middle itself if (arr == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); // We reach here when element is not present // in array return -1; // Driver method to thử nghiệm above public static void main(String args<>) BinarySearch ob = new BinarySearch(); int arr<> = 2, 3, 4, 10, 40 ; int n = arr.length; int x = 10; int result = ob.binarySearch(arr, 0, n - 1, x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at index " + result); Python 3

# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch (arr, l, r, x): # check base case if r >= l: mid = l + (r - l) // 2 # If element is present at the middle itself if arr == x: return mid # If element is smaller than mid, then it # can only be present in left subarray elif arr > x: return binarySearch(arr, l, mid-1, x) # Else the element can only be present # in right subarray else: return binarySearch(arr, mid + 1, r, x) else: # Element is not present in the array return -1 # Driver Code arr = < 2, 3, 4, 10, 40 > x = 10 # Function điện thoại tư vấn result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print ("Element is present at index % d" % result) else: print ("Element is not present in array") C#

// C# implementation of recursive Binary search using System; class GFG // Returns index of x if it is present in // arr, else return -1 static int binarySearch(int<> arr, int l, int r, int x) if (r >= l) int mid = l + (r - l) / 2; // If the element is present at the // middle itself if (arr == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); // We reach here when element is not present // in array return -1; // Driver method to kiểm tra above public static void Main() int<> arr = 2, 3, 4, 10, 40 ; int n = arr.Length; int x = 10; int result = binarySearch(arr, 0, n - 1, x); if (result == -1) Console.WriteLine("Element not present"); else Console.WriteLine("Element found at index " + result); PHP

= $l) $mid = ceil($l + ($r - $l) / 2); // If the element is present // at the middle itself if ($arr<$mid> == $x) return floor($mid); // If element is smaller than // mid, then it can only be // present in left subarray if ($arr<$mid> > $x) return binarySearch($arr, $l, $mid - 1, $x); // Else the element can only // be present in right subarray return binarySearch($arr, $mid + 1, $r, $x); // We reach here when element // is not present in array return -1; // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo "Element is not present in array"; elseecho "Element is present at index ", $result; ?> Kết quả:

Element is present at index 3

2.2 tiến hành lặp đi tái diễn để tìm kiếm nhị phân(Binary Search)

C++

// C++ program khổng lồ implement recursive Binary search #include using namespace std; // A iterative binary tìm kiếm function. It returns // location of x in given array arr if present, // otherwise -1 int binarySearch(int arr<>, int l, int r, int x) { while (l C

// C program khổng lồ implement iterative Binary tìm kiếm #include // A iterative binary tìm kiếm function. It returns // location of x in given array arr if present, // otherwise -1 int binarySearch(int arr<>, int l, int r, int x) { while (l Java

// Java implementation of iterative Binary tìm kiếm class BinarySearch { // Returns index of x if it is present in arr<>, // else return -1 int binarySearch(int arr<>, int x) { int l = 0, r = arr.length - 1; while (l Python 3

# Python3 code lớn implement iterative Binary # Search. # It returns location of x in given array arr # if present, else returns -1 def binarySearch(arr, l, r, x): while l C#

// C# implementation of iterative Binary tìm kiếm using System; class GFG { // Returns index of x if it is present in arr<>, // else return -1 static int binarySearch(int<> arr, int x) { int l = 0, r = arr.Length - 1; while (l PHP


Kết quả:

Element is present at index 3

3. Độ phức tạp

Thời gian phức tạp:

Độ phức tạp về thời hạn của tìm kiếm nhị phân rất có thể được viết là

T(n) = T(n/2) + c

Sự tái diễn ở trên hoàn toàn có thể được giải quyết bằng cách sử dụng cách thức đệ quy tree hoặc phương thức Master. Nó bên trong trường đúng theo II của phương thức Master và giải pháp của sự tái diễn là θ (Logn).

Xem thêm: Top 9 Game Bóng Đá Hay Cho Pc Cộng Đông Gamer Đánh Giá Cao, # Top 50 Game Bóng Đá Offline Pc Hay Nhất

Không gian phụ trợ: O (1) trong trường hợp tiến hành lặp đi lặp lại. Vào trường hợp tiến hành đệ quy, không gian ngăn xếp gọi đệ quy O (Logn).

Nguồn và Tài liệu giờ đồng hồ anh tham khảo:

Tài liệu trường đoản cú diyxaqaw.com:

Nếu bạn thấy hay và hữu ích, chúng ta cũng có thể tham gia những kênh sau của diyxaqaw.com để nhận được không ít hơn nữa: