Cách tiếp cận này sẽ sử dụng kiểu boolean thực tế [và phân giải thành true và false] nếu trình biên dịch hỗ trợ nó. [cụ thể là C++]
Tuy nhiên, sẽ tốt hơn nếu kiểm tra xem C++ có đang được sử dụng hay không [thông qua macro __cplusplus] và thực sự sử dụng true và false
Nếu muốn thực hành các chương trình về cấu trúc dữ liệu và thuật toán, bạn có thể xem qua các câu hỏi phỏng vấn về cấu trúc dữ liệu và thuật toán
Trong bài đăng này, chúng ta sẽ xem cách tìm kiếm một phần tử trong mảng được sắp xếp và xoay
Vấn đề
Bạn được cung cấp một mảng được sắp xếp và xoay như bên dưới
1
2
3
int arr[] = {16,19,21,25,3,5,8,10};
Nếu bạn lưu ý rằng mảng được sắp xếp và xoay. Bạn cần tìm kiếm một phần tử trong mảng trên với độ phức tạp thời gian o[log n]
Giải pháp
Bạn có thể tìm kiếm một phần tử trong mảng trên bằng tìm kiếm tuyến tính nhưng điều đó sẽ mất o[n]
Bạn có thể sử dụng biến thể của thuật toán tìm kiếm nhị phân để giải quyết vấn đề trên. Bạn có thể sử dụng một thuộc tính mà bạn có thể chia mảng thành hai mảng con được sắp xếp [{16,19,21,25},{3,5,8,10} ], mặc dù bạn không cần tìm điểm trục [Các phần tử bắt đầu giảm dần
thuật toán
- tính toán giữa tôi. e thấp+cao/2
- Kiểm tra xem a[mid…high] đã được sắp xếp chưa
- Nếu số nằm giữa phạm vi , low=mid+1
- Nếu số không nằm trong phạm vi, cao=giữa-1
- Kiểm tra xem a[low. giữa] được sắp xếp
- Nếu số nằm trong phạm vi, cao=trung bình 1
- Nếu số không nằm trong phạm vi,low=mid+1
Hãy hiểu điều này với sự giúp đỡ của ví dụ
Các bước liên quan để tìm kiếm 5 trong mảng trên
- tính toán giữa tôi. e. 3 [0+7/2]
- a[mid][25] > a[high][10] && 5 < a[low][16] && 5< a[high] [25], vì vậy số [5] nằm ở phần bên phải, nên giá trị thấp sẽ trở thành
- a[mid] ==5, vì vậy bạn có thể trả lại
Chương trình Java để tìm kiếm một phần tử trong một mảng được sắp xếp và xoay
Tạo một lớp có tên
SearchElementSortedAndRotatedArrayMain. java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
gói org. arpit. java2blog;
lớp công khai SearchElementSortedAndRotatedArrayMain {
công khai tĩnh vô hiệu chính[String[] args] {
int arr[]={16,19,21,25,3,5,8,10};
Hệ thống. ra. println["Chỉ mục của phần tử 5. " + findElementRotatedSortedArray[arr . 0,arr.độ dài - 1,5]];
}
công khai tĩnh int findElementRotatedSortedArray[int[] arr,int low,int high,int number]
{
int mid;
trong khi[thấp