Tìm kiếm trong mảng được sắp xếp xoay vòng Java

• Khởi tạo hàm đệ quy với 2 con trỏ left = 0, right = n – 1
• Tìm phần giữa của dải mid = [trái + phải] / 2
• Nếu phạm vi [trái, giữa] được sắp xếp,
  • Nếu mục tiêu nằm trong phạm vi đó, hãy đệ quy chuyển đến phạm vi [trái, giữa]
  • Khác đi đến phạm vi [giữa + 1, phải]
• Khác, chúng tôi chuyển đến phạm vi [giữa + 1, bên phải] [vì nó phải được sắp xếp],
  • Nếu mục tiêu nằm trong phạm vi, hãy đệ quy chuyển đến phạm vi [giữa + 1, phải]
  • Khác đi đến phạm vi [trái, giữa].  

Thực hiện

Mã C++

int findInArray[vector < int > & a, int left, int right, int target] {
  if [left > right] {
    return -1;
  }
  int mid = [left + right] / 2;
  if [a[mid] == target] {
    return mid;
  }
  if [a[mid] >= a[left]] {
    if [target >= a[left] && target <= a[mid]] {
      return findInArray[a, left, mid - 1, target];
    } else {
      return findInArray[a, mid + 1, right, target];
    }
  } else {
    if [target >= a[mid] && target <= a[right]] {
      return findInArray[a, mid + 1, right, target];
    } else {
      return findInArray[a, left, mid - 1, target];
    }
  }
}

Mã Java

public static int findInArray[int[] a, int left, int right, int target] {
  if [left > right] {
    return -1;
  }
  int mid = [left + right] / 2;
  if [a[mid] == target] {
    return mid;
  }
  if [a[mid] >= a[left]] {
    if [target >= a[left] && target <= a[mid]] {
      return findInArray[a, left, mid - 1, target];
    } else {
      return findInArray[a, mid + 1, right, target];
    }
  } else {
    if [target >= a[mid] && target <= a[right]] {
      return findInArray[a, mid + 1, right, target];
    } else {
      return findInArray[a, left, mid - 1, target];
    }
  }
}

Mã Python

def findInArray[a, left, right, target]:
    if left > right:
        return -1
    mid = [left + right] // 2
    if a[mid] == target:
        return mid
    if a[mid] >= a[left]:
        if target >= a[left] and target <= a[mid]:
            return findInArray[a, left, mid - 1, target]
        else:
            return findInArray[a, mid + 1, right, target]
    else:
        if target >= a[mid] and target <= a[right]:
            return findInArray[a, mid + 1, right, target]
        else:
            return findInArray[a, left, mid - 1, target]

Phân tích độ phức tạp

• Thời gian phức tạp. O[log2n]
• Độ phức tạp không gian. Ô[1]

Vấn đề thực hành

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

câu hỏi thường gặp

1. Phương pháp tìm kiếm nhị phân có hoạt động không nếu mảng có các phần tử trùng lặp?

A. Cách tiếp cận sẽ không hoạt động nếu mảng có các phần tử trùng lặp vì chúng tôi sẽ không thể quyết định nên lặp lại cho nửa bên trái hay bên phải, trong trường hợp xảy ra trùng lặp

2. Các trường hợp cơ sở cho phương pháp đệ quy này là gì?

A. Nếu con trỏ bên trái vượt quá con trỏ bên phải, hàm trả về -1. Ngoài ra, nếu phần tử hiện tại, bằng phần tử đích, chúng tôi trả về chỉ mục của phần tử này. Đây là những trường hợp cơ bản của đệ quy

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

Cách nhanh nhất để tìm kiếm một mảng được sắp xếp là gì?

Độ phức tạp về thời gian của việc tìm một số trong một mảng được sắp xếp xoay là bao nhiêu?

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?