binary search in java

phiphi136

New member
## Tìm kiếm nhị phân trong Java

Tìm kiếm nhị phân là một thuật toán tìm kiếm tìm thấy vị trí của giá trị đích trong một mảng được sắp xếp.Nó hoạt động bằng cách liên tục chia mảng làm đôi cho đến khi tìm thấy giá trị mục tiêu.

Độ phức tạp của thời gian của tìm kiếm nhị phân là O (log n), có nghĩa là thời gian chạy của thuật toán là logarit trong kích thước của mảng.Điều này làm cho tìm kiếm nhị phân trở thành một thuật toán rất hiệu quả để tìm kiếm các mảng lớn.

### Thuật toán

Sau đây là mã giả cho tìm kiếm nhị phân:

`` `
Function BinarySearch (mảng, mục tiêu) {
// 1. Khởi tạo các con trỏ trái và phải.
trái = 0;
phải = mảng.length - 1;

// 2. Trong khi con trỏ bên trái nhỏ hơn hoặc bằng con trỏ bên phải,
while (trái <= phải) {
// 3. Tính chỉ số giữa.
mid = (trái + phải) / 2;

// 4. Nếu giá trị đích bằng với phần tử ở chỉ số giữa,
if (mảng [mid] == target) {
// 5. Trả lại chỉ số giữa.
trở lại giữa;
}

// 6. Nếu không, nếu giá trị đích nhỏ hơn phần tử ở chỉ số giữa,
khác if (target <mảng [mid]) {
// 7. Cập nhật con trỏ bên phải nhỏ hơn chỉ mục giữa.
Phải = giữa - 1;
}

// 8. Nếu không, nếu giá trị đích lớn hơn phần tử ở chỉ số giữa,
khác {
// 9. Cập nhật con trỏ bên trái lớn hơn chỉ số giữa.
trái = mid + 1;
}
}

// 10. Nếu không tìm thấy giá trị đích, hãy trả về -1.
trả lại -1;
}
`` `

### ví dụ

Hãy xem xét một số ví dụ về cách tìm kiếm nhị phân hoạt động.

#### Ví dụ 1

Xem xét các mảng số sau:

`` `
[1, 3, 5, 7, 9]
`` `

Nếu chúng ta muốn tìm vị trí của số 5, chúng ta sẽ bắt đầu bằng cách đặt con trỏ bên trái thành 0 và con trỏ bên phải thành 4. Chỉ số giữa sẽ là 2, đó là chỉ số của số 5. Do đó, nhị phânThuật toán tìm kiếm sẽ trả về giá trị 2.

#### Ví dụ 2

Bây giờ, hãy xem xét các mảng số sau:

`` `
[-1, 0, 1, 2, 3]
`` `

Nếu chúng ta muốn tìm vị trí của số 2, chúng ta sẽ bắt đầu bằng cách đặt con trỏ bên trái thành 0 và con trỏ bên phải thành 4. Chỉ số giữa sẽ là 2, đó là chỉ mục của số 1. Vì giá trị đíchlớn hơn phần tử ở chỉ số giữa, chúng tôi sẽ cập nhật con trỏ bên trái lớn hơn chỉ số giữa, là 3. Chỉ số giữa sau đó sẽ là 3, là chỉ số của số 2. Do đó, nhị phânThuật toán tìm kiếm sẽ trả về giá trị 3.

### Thực hiện

Sau đây là việc triển khai thuật toán tìm kiếm nhị phân trong Java:

`` `java
nhập java.util.arrays;

lớp công khai BinarySearch {

public static int nhị phân nghiên cứu (int [] mảng, int target) {
// 1. Khởi tạo các con trỏ trái và phải.
int trái = 0;
int right = mảng.length - 1;

// 2. Trong khi con trỏ bên trái nhỏ hơn hoặc bằng con trỏ bên phải,
while (trái <= phải) {
// 3. Tính chỉ số giữa.
int mid = (trái + phải) / 2;

// 4. Nếu giá trị đích bằng với phần tử ở chỉ số giữa,
if (mảng [mid] == target) {
// 5. Trả lại chỉ số giữa.
=======================================
## Binary Search in Java

Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the array in half until the target value is found.

The time complexity of binary search is O(log n), which means that the algorithm's runtime is logarithmic in the size of the array. This makes binary search a very efficient algorithm for searching large arrays.

### Algorithm

The following is the pseudocode for binary search:

```
function binarySearch(array, target) {
// 1. Initialize the left and right pointers.
left = 0;
right = array.length - 1;

// 2. While the left pointer is less than or equal to the right pointer,
while (left <= right) {
// 3. Calculate the middle index.
mid = (left + right) / 2;

// 4. If the target value is equal to the element at the middle index,
if (array[mid] == target) {
// 5. Return the middle index.
return mid;
}

// 6. Otherwise, if the target value is less than the element at the middle index,
else if (target < array[mid]) {
// 7. Update the right pointer to be one less than the middle index.
right = mid - 1;
}

// 8. Otherwise, if the target value is greater than the element at the middle index,
else {
// 9. Update the left pointer to be one greater than the middle index.
left = mid + 1;
}
}

// 10. If the target value is not found, return -1.
return -1;
}
```

### Examples

Let's look at some examples of how binary search works.

#### Example 1

Consider the following array of numbers:

```
[1, 3, 5, 7, 9]
```

If we want to find the position of the number 5, we would start by setting the left pointer to 0 and the right pointer to 4. The middle index would then be 2, which is the index of the number 5. Therefore, the binary search algorithm would return the value 2.

#### Example 2

Now, let's consider the following array of numbers:

```
[-1, 0, 1, 2, 3]
```

If we want to find the position of the number 2, we would start by setting the left pointer to 0 and the right pointer to 4. The middle index would then be 2, which is the index of the number 1. Since the target value is greater than the element at the middle index, we would update the left pointer to be one greater than the middle index, which is 3. The middle index would then be 3, which is the index of the number 2. Therefore, the binary search algorithm would return the value 3.

### Implementation

The following is an implementation of the binary search algorithm in Java:

```java
import java.util.Arrays;

public class BinarySearch {

public static int binarySearch(int[] array, int target) {
// 1. Initialize the left and right pointers.
int left = 0;
int right = array.length - 1;

// 2. While the left pointer is less than or equal to the right pointer,
while (left <= right) {
// 3. Calculate the middle index.
int mid = (left + right) / 2;

// 4. If the target value is equal to the element at the middle index,
if (array[mid] == target) {
// 5. Return the middle index.
 
Join ToolsKiemTrieuDoGroup
Back
Top