Trong hướng dẫn này, bạn sẽ học cách sắp xếp Tìm kiếm nhị phân hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của Tìm kiếm nhị phân trong C, C ++, Java và Python.
Tìm kiếm nhị phân là một thuật toán tìm kiếm để tìm vị trí của một phần tử trong một mảng được sắp xếp.
Trong cách tiếp cận này, phần tử luôn được tìm kiếm ở giữa một phần của mảng.
Tìm kiếm nhị phân chỉ có thể được thực hiện trên một danh sách các mục đã được sắp xếp. Nếu các phần tử chưa được sắp xếp, chúng ta cần sắp xếp chúng trước.
Tìm kiếm nhị phân hoạt động
Thuật toán tìm kiếm nhị phân có thể được thực hiện theo hai cách được thảo luận dưới đây.
- Phương pháp lặp lại
- Phương pháp đệ quy
Phương pháp đệ quy tuân theo cách tiếp cận chia để trị.
Các bước chung cho cả hai phương pháp được thảo luận dưới đây.
- Mảng mà việc tìm kiếm được thực hiện là:
Mảng ban đầu
Gọix = 4
là phần tử cần tìm kiếm. - Đặt hai con trỏ thấp và cao lần lượt ở các vị trí thấp nhất và cao nhất.
Thiết lập con trỏ
- Tìm phần tử giữa ở giữa của mảng tức là.
(arr(low + high)) / 2 = 6
.Yếu tố giữa
- Nếu x == mid thì trả về mid.Else, so sánh phần tử cần tìm với m.
- Nếu
x> mid
, so sánh x với phần tử giữa của các phần tử ở bên phải của giữa. Điều này được thực hiện bằng cách đặt thấp thànhlow = mid + 1
. - Khác, so sánh x với phần tử giữa của các phần tử ở bên trái của phần giữa. Điều này được thực hiện bằng cách đặt cao thành
high = mid - 1
.Tìm phần tử giữa
- Lặp lại các bước từ 3 đến 6 cho đến khi mức thấp gặp mức cao.
Yếu tố giữa
x = 4
được tìm thấy.Tìm
Thuật toán tìm kiếm nhị phân
Phương pháp lặp lại
làm cho đến khi các con trỏ thấp và cao gặp nhau. mid = (low + high) / 2 if (x == arr (mid)) trả về mid else if (x> A (mid)) // x ở phía bên phải low = mid + 1 else // x đang bật cao bên trái = giữa - 1
Phương pháp đệ quy
binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else if x <data (mid) // x nằm trên bên phải trả về binarySearch (arr, x, mid + 1, high) else // x ở bên phải trả về binarySearch (arr, x, low, mid - 1)
Ví dụ về Python, Java, C / C ++ (Phương pháp lặp)
Python Java C C ++ # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
// Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
// Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
// Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
Ví dụ về Python, Java, C / C ++ (Phương pháp đệ quy)
Python Java C C ++ # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
// Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
// Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
// Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
Độ phức tạp của tìm kiếm nhị phân
Thời gian phức tạp
- Trường hợp phức tạp tốt nhất :
O(1)
- Độ phức tạp của trường hợp trung bình :
O(log n)
- Trường hợp phức tạp tệ nhất :
O(log n)
Không gian phức tạp
Độ phức tạp không gian của tìm kiếm nhị phân là O(n)
.
Ứng dụng tìm kiếm nhị phân
- Trong các thư viện Java, .Net, C ++ STL
- Trong khi gỡ lỗi, tìm kiếm nhị phân được sử dụng để xác định vị trí xảy ra lỗi.