Thuật toán tìm kiếm Nhị phân - Thuật toán Binary search trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 890

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Thuật toán tìm kiếm nhị phân trong C++ dùng để tìm kiếm phần tử trong danh sách (hay một mảng) đã sắp xếp. Với thuật toán tìm kiếm nhị phân bạn có thể tìm kiếm nhanh hơn so với thuật toán tìm kiếm tuyến tính nhưng chậm hơn so với bảng băm.

    [​IMG]



    http://www.mediafire.com/?nh5g8be463brqnb

    Tuy nhiên thuật toán Binary Search trong C++ có một số nhược điểm như nếu danh sách bị thay đổi (chèn, xóa, thay đổi phần tử) chúng ta sẽ phải sắp xếp lại các phần tử. Việc này tốn nhiều thời gian.

    Ý tưởng thuật toán tìm kiếm nhị phân:
    • Với một danh sách (hay một mảng) đã sắp xếp cho trước.
    • Thuật toán Binary search sẽ tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh với x (x là gia trị cần tìm kiếm) bằng cách chia danh sách ban đầu thành 2 danh sách con.
    • Sau đó thuật toán sẽ so sánh x với giá trị của phần tử giữa của danh sách Mid = (Start + Finish)/2.
    • Nếu x > Mid thì sẽ đi tìm các phần tử ở danh sách con phía sau phần tử Mid.
    • Ngược lại sẽ tìm kiếm ở danh sách trước phần tử Mid.
    • Trong mỗi lần tìm kiếm ở danh sách con, thuật toán lại tiếp tục chia nhỏ danh sách con đó thành 2 danh sách con nhỏ hơn và lặp lại việc so sách phần tử giữa Mid với x.

    Cài đặt thuật toán tìm kiếm nhị phân Binary Search trong C++

    Mã:
    void bsearch (int* a, int start, int finish, int x){
        if (start == finish){
            if (a[start] == x) return start;
            else return -1;
        } else {
            int mid = (start + finish)/2;
            if (a[mid] == x) return mid;
            else if (a[mid] > x) return bsearch(a, start, mid - 1, x);
                else return (a, mid + 1, finish, x);
          
        }
    }
    Độ phức tạp của thuật toán : O(log n)

    Chúc các bạn học tập tốt !!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap