Giải phương trình bằng phương pháp chia đôi Java

Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Binary Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết[khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…] về Binary Search thông qua các phần sau.

1. Giới thiệu

Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính[Linear Search], độ phức tạp thời gian của thuật toán trên là O [n]. Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

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

Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O [Log n].

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

1. So sánh x với phần tử ở giữa.
2. Nếu x khớp với phần tử giữa, chúng ta trả về chỉ số giữa.
3. Ngược lại Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng ta tái diễn cho một nửa bên phải.
4. Ngược lại [x nhỏ hơn] lặp lại cho nửa bên trái.

2. Code ví dụ trên nhiều ngôn ngữ

2.1 Triển khai đệ quy với Tìm kiếm nhị phân[Binary Search]

C++

// C++ program to implement recursive Binary Search #include using namespace std; // A recursive binary search function. It returns // location of x in given array arr[l..r] 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[mid] == x] return 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; } 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 = l] { int mid = l + [r - l] / 2; // If the element is present at the // middle itself if [arr[mid] == x] return 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 method to test 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[mid] == x: return mid # If element is smaller than mid, then it # can only be present in left subarray elif arr[mid] > 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 Binary Search using System; class GFG { // Returns index of x if it is present in // arr[l..r], 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[mid] == x] return 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 method to test 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

Kết quả:

Element is present at index 3

2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân[Binary Search]

C++

// C++ program to implement recursive Binary Search #include using namespace std; // A iterative binary search function. It returns // location of x in given array arr[l..r] if present, // otherwise -1 int binarySearch[int arr[], int l, int r, int x] { while [l