Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
672 views
in Technique[技术] by (71.8m points)

data structures - Why is Binary Search a divide and conquer algorithm?

I was asked if a Binary Search is a divide and conquer algorithm at an exam. My answer was yes, because you divided the problem into smaller subproblems, until you reached your result.

But the examinators asked where the conquer part in it was, which I was unable to answer. They also disapproved that it actually was a divide and conquer algorithm.

But everywhere I go on the web, it says that it is, so I would like to know why, and where the conquer part of it is?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The book

Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss

Says that a D&C algorithm should have two disjoint recursive calls. I.e like QuickSort. Binary Search does not have this, even if it can be implemented recursively, so I guess this is the answer.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...