Chào ace, bài bác này bọn họ vẫn tò mò về một trong số thuật toán thù sắp xếp được áp dụng các vào thiết kế với thực tiễn độc nhất vô nhị sẽ là Binary Search, dưới đây kulturbench.com vẫn reviews cùng chia sẻ chi tiết(quan niệm, ứng dụng của chính nó, code ví dụ, ưu thế, điểm yếu…) về Binary Search thông qua các phần sau.

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


1. Giới thiệu

Cho một mảng vẫn bố trí arr <> bao gồm n bộ phận, hãy viết một hàm nhằm tìm tìm 1 phần tử x đã mang lại vào arr <>.

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

Tìm kiếm nhị phân(Binary Search): Tìm kiếm một mảng được thu xếp bằng phương pháp chia đôi khoảng chừng thời hạn tra cứu kiếm những lần. Bắt đầu với một khoảng chừng bao hàm toàn bộ mảng. Nếu cực hiếm của key kiếm tìm tìm bé dại hơn mục nghỉ ngơi khoảng tầm thân, hãy thu hạn hẹp khoảng chừng kia xuống nửa bên dưới. Nếu không, hãy thu dong dỏng nó sinh hoạt nửa trên. Lặp lại kiểm tra cho tới Khi quý hiếm được search thấy hoặc khoảng tầm thời gian trống.


*

Ý tưởng của kiếm tìm kiếm nhị phân là thực hiện thông báo mà mảng được bố trí với bớt độ phức tạp về thời gian thành O (Log n).

Xem thêm: Shark Phi Là Ai ? Tiểu Sử Đầy Đủ Nhất Về… Tiểu Sử Shark Trương Lý Hoàng Phi

Về cơ bản bọn họ vứt qua 1 nửa số thành phần chỉ sau một lần đối chiếu.

So sánh x với phần tử chính giữa.Nếu x khớp với phần tử thân, họ trả về chỉ số giữa.Ngược lại Nếu x lớn hơn phần tử thân, thì x chỉ hoàn toàn có thể phía trong nửa mảng bé bên đề nghị sau thành phần giữa. Vì vậy, chúng ta tái diễn cho 1 nửa mặt cần.Ngược lại (x bé dại hơn) lặp lại mang lại nửa phía bên trái.

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

2.1 Triển knhì đệ quy với Tìm kiếm nhị phân(Binary Search)

C++

// C++ program to lớn implement recursive sầu Binary Search #include using namespace std; // A recursive sầu 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 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 Search #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 lớn thử nghiệm above sầu 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): # Cheông chồng 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 call 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 sầu 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 thử nghiệm above sầu 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)) emang đến "Element is not present in array"; elseeđến "Element is present at index ", $result; ?> Kết quả:

Element is present at index 3

2.2 Thực hiện nay lặp đi lặp lại nhằm Tìm tìm nhị phân(Binary Search)

C++

// C++ program lớn implement recursive Binary Search #include using namespace std; // A iterative sầu 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 to implement iterative sầu Binary Search #include // A iterative sầu 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 sầu Binary Search 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 khổng lồ implement iterative sầu 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 Search 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 hợp về thời gian của Tìm kiếm nhị phân có thể được viết là

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

Sự tái diễn sinh hoạt bên trên hoàn toàn có thể được xử lý bằng phương pháp thực hiện phương thức đệ quy tree hoặc cách thức Master. Nó phía trong trường phù hợp II của Phương thơm pháp Master cùng phương án của sự tái diễn là θ (Logn).

Xem thêm: Định Tuyến Tĩnh Là Gì - Bài 1: Định Tuyến Tĩnh

Không gian phụ trợ: O (1) trong ngôi trường hòa hợp tiến hành lặp đi lặp lại. Trong trường thích hợp thực hiện đệ quy, không gian ngăn xếp hotline đệ quy O (Logn).

Nguồn cùng Tài liệu giờ đồng hồ anh tđắm say khảo:

Tài liệu tự kulturbench.com:

Nếu chúng ta thấy giỏi và hữu dụng, chúng ta cũng có thể tmê mệt gia những kênh sau của kulturbench.com nhằm dấn được rất nhiều hơn nữa:


Chuyên mục: ĐỊNH NGHĨA
Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *