Tìm kiếm trong studio mã mảng được sắp xếp xoay

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<=high)

        {

            trung bình = thấp + ((high - low) / 2);;

            if(arr[mid]==number)

            {

                        trả lại giữa;

            }

            if(arr[mid]<=arr[high])

            {

                // Đã sắp xếp phần bên phải

                        nếu(số > arr[mid] && number <=arr[high])

{

thấp=trung bình+1;

                }

                khác

                {

                    cao = trung bình - 1;

                }

            }

            else

            {

                // Phần bên trái được sắp xếp

                        nếu(arr[low]<=number && number < arr[mid])

{

cao=trung bình 1;

                }

                khác

                {

                    thấp = trung bình + 1;

                }

            }

        }

        trả lại - 1;

    }

}

1

2

3

Chỉ mục của phần tử 5 . 5

Bài đăng này có hữu ích không?

Hãy cho chúng tôi biết nếu bạn thích bài viết. Đó là cách duy nhất chúng ta có thể cải thiện

Đúng

Không

nhập_liên hệ

Bạn cũng có thể thích

Tìm kiếm Leetcode dãy – Tìm vị trí đầu và cuối của phần tử trong mảng đã sắp xếp

Sắp xếp một mảng gồm 0, 1 và 2

Kiểm tra xem có thể đi đến cuối Mảng đã cho bằng cách Nhảy không

Kiểm tra xem các phần tử mảng có liên tiếp không

Tìm cực tiểu cục bộ trong mảng

Cửa sổ trượt tối đa trong java

Đếm số lần xuất hiện (hoặc tần suất) của từng phần tử trong một mảng được sắp xếp

Tìm các mảng con với tổng đã cho trong một mảng

Đếm 1 trong Mảng nhị phân được sắp xếp

Tìm phần tử đỉnh trong mảng

• 2
• 3
• 4
• ›

Bạn sẽ tìm kiếm như thế nào trong danh sách được sắp xếp xoay vòng?

Thuật toán nào có thể được sử dụng để tìm một phần tử trong một mảng đã được sắp xếp?

Pivot trong mảng được sắp xếp xoay là gì?

Làm cách nào để tìm phần tử trục trong mảng trong C?