Хайлтын алгоритмууд

Sainbayar Batbaatar

• 2023-04-08

Шугаман хайлт ба хоёртын хайлтын кодын хэрэгжилт ба нарийн төвөгтэй байдлын шинжилгээ.

Хайлтын алгоритмууд нь хөгжүүлэгчийн хувьд ойлгох ёстой компьютерийн шинжлэх ухааны үндсэн ойлголт юм. Тэд өгөгдлийн цуглуулгын дунд тодорхой өгөгдлийг олохын тулд алхам алхмаар аргыг ашигладаг.

Хайлтын алгоритмууд нь хөгжүүлэгчийн хувьд ойлгох ёстой компьютерийн шинжлэх ухааны үндсэн ойлголт юм.

Хайлтын асуудлыг шийддэг аливаа алгоритм, тухайлбал зарим өгөгдлийн бүтцэд хадгалагдсан, эсвэл асуудлын домэйны хайлтын орон зайд тооцоолсон, салангид эсвэл тасралтгүй утгуудын аль нэгээр нь олж авах.

Хайлтын алгоритмын төрлүүд

1. Linear or Sequential Search
2. Binary Search

Энэ алгоритм нь зорилтот элемент олдох хүртэл бүх массив эсвэл жагсаалтыг нэг төгсгөлөөс дараалан давтах замаар ажилладаг. Хэрэв элемент олдвол индексээ буцаана, эс тэгвээс -1.

arr = [2, 12, 15, 11, 7, 19, 45]

Бидний хайхыг хүсэж буй зорилтот элемент  7 байна гэж бодъё.

Шугаман эсвэл дараалсан хайлт хийх арга:

0 индексээс эхэлж элемент бүрийг зорилттой харьцуул Хэрэв зорилтот элемент нь тухайн элементтэй тэнцүү байвал индексийг нь буцаана Хэрэв зорилго олдохгүй бол -1-ийг буцаана.

Java хэл дээрх шугаман эсвэл дараалсан хайлт.

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

Python хэл дээрх шугаман эсвэл дараалсан хайлт.

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Time Complexity

Best case нь зорилтот элемент нь массивын эхний элемент байх үед тохиолддог. Энэ тохиолдолд харьцуулах тоо нь 1. Тэгэхээр O(1) байна.

Average case дунджаар зорилтот элемент нь массивын дунд хэсэгт байх болно. Энэ тохиолдолд харьцуулах тоо N/2 байна. Тиймээс O(N) байх болно.

Worst case зорилтот элемент нь массивын хамгийн сүүлчийн элемент эсвэл массив дотор байхгүй үед хамгийн муу тохиолдол гардаг. Энэ тохиолдолд бид массивыг бүхэлд нь туулах ёстой тул харьцуулах тоо нь N байх болно. Тиймээс O(N) болно.

Хоёртын хайлт

Энэ төрлийн хайлтын алгоритм нь эрэмбэлэгдсэн массив дахь тодорхой утгын байрлалыг олоход хэрэглэгддэг. Хоёртын хайлтын алгоритм нь divide and conquer зарчмаар ажилладаг бөгөөд ажиллахад илүү хурдан байдаг тул хайлтын хамгийн сайн алгоритм гэж тооцогддог.

arr = [2, 12, 15, 17, 27, 29, 45]

Xайх зорилтот элемент нь  17 гэж бодъё.

Хоёртын хайлтын арга:

• Зорилтот элементийг массивын голын элементтэй харьцуулна.
• Хэрэв зорилтот элемент нь голын элементээс их байвал хайлт баруун хагасруу явна.
• Хэрэв зорилтот элемент нь голын утгаас бага байвал хайлт зүүн хагасруу явна.
• Голын элемент нь зорилтот элементтэй тэнцэх эсвэл зорилтот элемент массив дотор байхгүй болтол энэ процесс давтагдана.
• Хэрэв зорилтот элемент олдвол индексийг буцаана, эс тэгвээс -1-ийг буцаана.

Java хэл дээрх хоёртын хайлт

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

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

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

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Binary Search in Python

def search(nums, target):
    start = 0
    end = len(nums)-1

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


        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid

    return -1


if __name__ == '__main__':
    nums = [2, 12, 15, 17, 27, 29, 45]
    target = 17
    print(search(nums, target))

Time Complexity

Best case нь зорилтот элемент нь массивын дунд элемент байх үед тохиолддог. Энэ тохиолдолд харьцуулах тоо нь 1. Тэгэхээр O(1) байна.

Best case нь дунджаар зорилтот элемент нь массивын хаа нэгтээ байх болно. Тиймээс O(logN) байх болно.

Best case нь зорилтот элемент жагсаалтад байхгүй эсвэл голын элементээс хол байх үед тохиолддог. Тиймээс O(logN) байх болно.

Нийтлэл бичсэн: Б. Сайнбаяр