演算法的divide-and-conquer的問題3

Does binary search use the divide-and-conquer strategy?

1 Answer

Rating
  • Leslie
    Lv 7
    9 years ago
    Favorite Answer

    Binary search is a divide-and-conquer (D&C) strategy.It first compares the query key q with the "middle element".

    if equal, we are done.

    Otherwise, it divides the range into two parts.

    One part does not have the answer,

    while the other part can be searched for q recursively,

    until it is found or fails to exist (the part contains no element).This kind of divide-and-conquer has a special name: Decrease-and-Conquer.

    On the case of binary search, it is a decrease-by-half D&C.

Still have questions? Get your answers by asking now.