On some generalizations of binary search

David Dobkin; R. J. Lipton

doi:10.1145/800119.803909

On some generalizations of binary search

David Dobkin, R. J. Lipton

Research output: Contribution to journal › Conference article › peer-review

8 Scopus citations

Abstract

Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.

Original language	English (US)
Pages (from-to)	310-316
Number of pages	7
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800119.803909
State	Published - Jan 1 1974
Event	6th Annual ACM Symposium on Theory of Computing, STOC 1974 - Seattle, United States Duration: Apr 30 1974 → May 2 1974

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800119.803909

Cite this

@article{739be87b2a6e48fca8088b7d745d78f3,

title = "On some generalizations of binary search",

abstract = "Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.",

author = "David Dobkin and Lipton, {R. J.}",

note = "Publisher Copyright: {\textcopyright} Association for Computing Machinery. All rights reserved.; 6th Annual ACM Symposium on Theory of Computing, STOC 1974 ; Conference date: 30-04-1974 Through 02-05-1974",

year = "1974",

month = jan,

day = "1",

doi = "10.1145/800119.803909",

language = "English (US)",

pages = "310--316",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - On some generalizations of binary search

AU - Dobkin, David

AU - Lipton, R. J.

PY - 1974/1/1

Y1 - 1974/1/1

N2 - Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.

AB - Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.

UR - http://www.scopus.com/inward/record.url?scp=84915563737&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84915563737&partnerID=8YFLogxK

U2 - 10.1145/800119.803909

DO - 10.1145/800119.803909

M3 - Conference article

AN - SCOPUS:84915563737

SN - 0737-8017

SP - 310

EP - 316

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 6th Annual ACM Symposium on Theory of Computing, STOC 1974

Y2 - 30 April 1974 through 2 May 1974

ER -

On some generalizations of binary search

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this