Qidiruv algoritmlari chiziqli qidiruv va ikkilik qidiruv kodini amalga oshirish va murakkablik tahlili

Kodni amalga oshirish
Java-da buyurtma-agnostik ikkilik qidiruv
package algorithms.searching;


public class OrderAgnosticBinarySearch {
public static void main(String[] args) {
int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
int target = -1;
System.out.println(search(nums1, target));
System.out.println(search(nums2, target));
}


static int search(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;


boolean isAscending = arr[start] < arr[end];


while (start <= end) {
int mid = start + (end - start) / 2;


if (target == arr[mid])
return mid;


if (isAscending) {
if (target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (target < arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
Python-da buyurtma-agnostik ikkilik qidiruv
def search(nums, target):
start = 0
end = len(nums)-1


is_ascending = nums[start] < nums[end]


while start <= end:
mid = start + (end-start)//2


if target == nums[mid]:
return mid


if is_ascending:
if target < nums[mid]:
end = mid-1
else:
start = mid+1
else:
if target < nums[mid]:
start = mid+1
else:
end = mid-1


return -1
if __name__ == '__main__':
nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
target = -1
print(search(nums1, target))
print(search(nums2, target))
Vaqt murakkabligi tahlili
Vaqt murakkabligida hech qanday o'zgarish bo'lmaydi, shuning uchun u Binary Search bilan bir xil bo'ladi.
Xulosa
Ushbu maqolada biz ikkita eng muhim qidiruv algoritmini va ularning Python va Java-dagi kodlarini amalga oshirishni muhokama qildik. Biz ularning vaqt murakkabligi tahlilini ham ko'rib chiqdik.