Meta tags:
Headings (most frequently used words):
search, binary, procedure, of, performance, other, notes, alternative, for, finding, the, element, searches, contents, algorithm, versus, schemes, variations, history, implementation, issues, library, support, see, also, and, references, external, links, duplicate, elements, approximate, matches, space, complexity, derivation, average, case, additional, considerations, linear, trees, hashing, set, membership, algorithms, data, structures, uniform, exponential, interpolation, fractional, cascading, generalization, to, graphs, noisy, quantum, citations, sources, leftmost, rightmost, successful, unsuccessful, cost, comparison, branch, prediction, cache, usage,
Text of the page (most frequently used words):
the (665), #search (250), binary (172), displaystyle (169), and (131), for (125), log (118), array (77), element (75), that (74), target (60), are (54), this (53), can (49), with (45), case (45), edit (44), value (44), algorithm (42), elements (39), from (38), tree (38), than (38), average (38), searching (37), path (34), arrays (33), textstyle (33), procedure (32), lfloor (32), rfloor (32), knuth (31), number (29), sorted (29), which (29), doi (28), time (27), each (27), iteration (27), length (26), may (25), set (25), data (24), iterations (24), when (24), algorithms (23), 2016 (23), 1998 (22), trees (22), one (22), frac (22), internal (22), where (22), middle (22), two (21), external (20), worst (20), table (19), all (19), subsection (19), comparison (19), there (19), other (19), not (19), isbn (18), retrieved (18), function (18), searches (18), such (18), archived (17), computer (17), ordered (17), node (17), only (17), structures (16), comparisons (16), 978 (16), queries (16), linear (16), nodes (16), used (16), equal (16), finding (15), hash (15), has (15), original (15), range (15), fractional (15), cascading (15), interpolation (15), more (15), less (15), left (15), return (15), example (14), pdf (14), performance (14), then (14), position (14), right (14), unsuccessful (14), root (13), 1145 (13), acm (13), while (13), searched (13), approximate (13), most (13), faster (13), floor (13), wikipedia (12), index (12), programming (12), first (12), standard (12), library (12), april (12), half (12), its (12), because (12), keys (12), same (12), however (12), was (11), list (11), implementation (11), quantum (11), lower (11), but (11), complexity (11), successful (11), also (11), matches (11), method (10), integers (10), s2cid (10), performed (10), any (10), every (10), uniform (10), efficiently (10), comparing (10), integer (10), using (9), published (9), upper (9), large (9), java (9), problem (9), space (9), based (9), some (9), article (9), values (9), given (9), would (9), makes (9), bit (9), above (9), about (8), use (8), articles (8), science (8), sorting (8), wesley (8), 2011 (8), march (8), computing (8), sum (8), noisy (8), hashing (8), rank (8), possible (8), requires (8), likely (8), within (8), require (8), vertex (8), next (8), operations (8), usually (8), membership (8), memory (8), rightmost (8), else (8), toggle (7), page (7), implementations (7), version (7), bounds (7), tables (7), order (7), deletion (7), functions (7), specific (7), key (7), will (7), lengths (7), paths (7), into (7), midpoint (7), provides (7), matching (7), whether (7), instead (7), main (7), between (7), exponential (7), they (7), equation (7), leftmost (7), access (6), 4th (6), addison (6), professional (6), wayne (6), sedgewick (6), vol (6), bentley (6), type (6), 2018 (6), journal (6), probability (6), bloom (6), history (6), paul (6), predecessor (6), contains (6), structure (6), these (6), bits (6), point (6), both (6), end (6), equally (6), plus (6), must (6), levels (6), similar (6), logarithm (6), another (6), insertion (6), loop (6), even (6), exactly (6), always (6), done (6), perform (6), smallest (6), largest (6), logarithmic (6), level (6), leq (6), additional (5), pseudocode (5), errors (5), links (5), binary_search (5), 2019 (5), 2002 (5), 2008 (5), michael (5), rust (5), sort (5), base (5), information (5), june (5), extra (5), chazelle (5), bernard (5), arxiv (5), symposium (5), theory (5), fast (5), optimal (5), graphs (5), variation (5), problems (5), khuong (5), lists (5), support (5), constant (5), result (5), initial (5), over (5), after (5), does (5), notes (5), solve (5), performing (5), returned (5), once (5), failed (5), found (5), size (5), very (5), store (5), correct (5), power (5), representing (5), least (5), exact (5), compare (5), find (5), works (5), greater (5), much (5), efficient (5), required (5), alternative (5), successor (5), contents (4), terms (4), foundation (4), short (4), peer (4), reviewed (4), graph (4), language (4), andrew (4), 1007 (4), 201 (4), donald (4), 1997 (4), 2006 (4), press (4), goldman (4), 2003 (4), std (4), 1016 (4), 1986 (4), known (4), october (4), 2022 (4), well (4), issn (4), higher (4), should (4), related (4), caches (4), branch (4), common (4), lowest (4), representation (4), takes (4), units (4), computation (4), slightly (4), represented (4), yields (4), out (4), children (4), lie (4), divided (4), their (4), since (4), record (4), numbers (4), floating (4), strings (4), implemented (4), although (4), addition (4), check (4), checks (4), often (4), wrong (4), cases (4), per (4), few (4), computers (4), certain (4), stored (4), either (4), otherwise (4), taking (4), best (4), close (4), variations (4), records (4), nearest (4), schemes (4), being (4), count (4), itself (4), ram (4), locations (4), child (4), reached (4), deepest (4), greatest (4), duplicate (4), hide (4), move (4), sidebar (4), languages (3), view (3), text (3), available (3), under (3), inc (3), august (3), open (3), wayback (3), different (3), wikidata (3), wikijournal (3), associative (3), dictionary (3), 2013 (3), book (3), reading (3), art (3), combinatorial (3), reference (3), 2000 (3), python (3), bisection (3), apple (3), mac (3), developer (3), binarysearch (3), util (3), package (3), cobol (3), bsearch (3), july (3), read (3), algorithmica (3), guibas (3), leonidas (3), tricks (3), proceedings (3), applied (3), analysis (3), random (3), quant (3), via (3), years (3), error (3), system (3), 2001 (3), communications (3), exercise (3), cuckoo (3), filter (3), judy (3), methods (3), minimum (3), lisp (3), eliminates (3), derivation (3), bottenbruch (3), hermann (3), 1962 (3), interval (3), simply (3), location (3), highest (3), designed (3), mix (3), running (3), cost (3), represent (3), therefore (3), present (3), applies (3), follows (3), notation (3), content (3), references (3), idea (3), see (3), framework (3), collection (3), respectively (3), ranges (3), many (3), made (3), indices (3), calculating (3), overflow (3), twenty (3), part (3), whose (3), until (3), numerous (3), computational (3), geometry (3), work (3), bounded (3), cannot (3), pair (3), been (3), types (3), generalization (3), queried (3), located (3), finds (3), multiple (3), pointers (3), second (3), small (3), way (3), near (3), account (3), visualization (3), stores (3), difference (3), current (3), specialized (3), take (3), long (3), regardless (3), encoding (3), filters (3), like (3), single (3), balanced (3), except (3), unlike (3), versus (3), tlb (3), accessed (3), cache (3), assuming (3), substituting (3), added (3), intervals (3), outside (3), reaches (3), neighbor (3), following (3), ceiling (3), continues (3), tools (3), topic (2), code (2), contact (2), privacy (2), policy (2), apply (2), organization (2), wikimedia (2), commons (2), license (2), last (2), 2026 (2), categories (2), date (2), dates (2), description (2), literature (2), org (2), string (2), dynamic (2), divide (2), conquer (2), linked (2), machine (2), september (2), saddle (2), river (2), new (2), jersey (2), 321 (2), stroustrup (2), robert (2), moffat (2), turpin (2), academic (2), coding (2), 2nd (2), 3rd (2), kasahara (2), morishita (2), college (2), sequence (2), processing (2), practical (2), fitzgerald (2), 2015 (2), ruby (2), 2009 (2), rivest (2), ronald (2), cormen (2), chang (2), shi (2), software (2), engineering (2), butterfield (2), ngondi (2), 7th (2), oxford (2), university (2), pearls (2), jon (2), sources (2), 2024 (2), primitive (2), slice (2), bisect (2), nsarray (2), microsoft (2), oracle (2), corporation (2), platform (2), edition (2), documentation (2), collections (2), manual (2), group (2), letters (2), research (2), 1988 (2), applications (2), technique (2), help (2), cite (2), lehmer (2), derrick (2), 1960 (2), 0113289 (2), 1957 (2), storage (2), peterson (2), william (2), grover (2), 032335 (2), review (2), rényi (2), magyar (2), pelc (2), andrzej (2), 3975 (2), theoretical (2), coping (2), 10th (2), meyer (2), 221 (2), probabilistic (2), liu (2), ding (2), jcss (2), sciences (2), intersection (2), dimension (2), conference (2), better (2), techniques (2), morin (2), pat (2), disks (2), symbol (2), what (2), answers (2), pvk (2), 2017 (2), 23752485 (2), mispredictions (2), implement (2), further (2), algol (2), 1971 (2), citations (2), exist (2), improve (2), have (2), ordinary (2), sentinel (2), mod (2), his (2), model (2), regular (2), grows (2), slowly (2), existing (2), compares (2), adding (2), minimized (2), minimizes (2), linearly (2), subtree (2), parent (2), big (2), factor (2), simplified (2), real (2), class (2), built (2), module (2), keeps (2), offers (2), static (2), classes (2), general (2), exit (2), conditions (2), defined (2), failure (2), programmers (2), variables (2), course (2), solution (2), several (2), incorrect (2), run (2), furthermore (2), own (2), contained (2), edge (2), straightforward (2), issues (2), worked (2), increasing (2), developed (2), back (2), tablet (2), names (2), were (2), classical (2), still (2), runs (2), 605 (2), approx (2), 433 (2), make (2), considered (2), tau (2), generalized (2), learns (2), undirected (2), positively (2), weighted (2), similarly (2), edges (2), subtrees (2), speeds (2), slower (2), extends (2), unbounded (2), bound (2), beforehand (2), subarray (2), adds (2), change (2), systems (2), inefficient (2), lookup (2), attribute (2), efficiency (2), ability (2), results (2), specifically (2), useful (2), themselves (2), filesystems (2), resulting (2), worse (2), fewest (2), including (2), simple (2), determining (2), cpu (2), cam (2), address (2), typical (2), four (2), smaller (2), processor (2), along (2), making (2), jump (2), usage (2), according (2), expressed (2), prediction (2), forms (2), consideration (2), increase (2), unsigned (2), expensive (2), considerations (2), reduced (2), called (2), doing (2), during (2), unique (2), positive (2), below (2), three (2), assumed (2), ends (2), here (2), 100 (2), ranks (2), endpoints (2), compute (2), equals (2), 5th (2), ceil (2), now (2), terminates (2), leave (2), eliminated (2), step (2), remaining (2), appearance (2), upload (2), file (2), changes (2), english (2), create (2), donate (2), menu (2), add, mobile, cookie, statement, statistics, developers, conduct, legal, safety, contacts, disclaimers, site, you, agree, registered, trademark, non, profit, creative, attribution, sharealike, rendered, parsoid, edited, utc, hidden, incorporating, publications, cs1, webarchive, template, dmy, featured, w2j, externally, https, php, title, oldid, 1371884285, topological, sweep, line, streaming, recursion, randomized, online, minimax, greedy, fold, traversal, depth, brute, force, breadth, backtracking, algorithmic, paradigms, trie, stack, segment, queue, heap, fenwick, benchmarks, variety, nist, wikibook, 56384, bjarne, condensed, web, kevin, 57351, alistair, hamburg, germany, kluwer, publishers, 7923, 7668, 4615, 0935, compression, 1st, 03804, 89685, 89683, fundamental, masahiro, shinichi, london, imperial, 86094, 635, scale, genome, kenneth, boca, raton, florida, 58488, 455, crc, guide, sally, sebastopol, california, 4919, 2601, reilly, media, pocket, mit, mcgraw, hill, 262, 03384, introduction, stein, clifford, leiserson, charles, thomas, kuo, knowledge, singapore, 981, 238, 348, world, scientific, gerard, 968897, 65788, 152, cfarray, network, 2012, 601, 598, ansi, unisys, 2020, dlang, 945, specifications, principles, ruggieri, salvatore, s0020, 0190, 00263, semi, google, blog, nearly, mergesorts, broken, bloch, joshua, textbook, 194, 52965, 53012, 190, sigcse, bulletin, pattis, richard, challenge, 191, 11232235, bf01840441, 163, 162, 12745042, bf01840440, 133, structuring, incompatibility, teaching, symposia, mathematics, 181, 9780821813102, 1090, psapm, 010, 180, a000225, oeis, addressing, 146, 1147, 0130, 130, ibm, development, 1996, 28th, philadelphia, 219, 237814, 237866, 9605043, 212, mechanical, database, lov, childs, landahl, parrilo, pablo, 2007, semidefinite, 41539957, 1103, physreva, 2007phrva, 75c2335c, bibcode, 0608161, physical, høyer, peter, neerbek, jan, yaoyun, complexities, distinctness, 448, 13717616, s00453, 002, 0976, 0102078, 429, alfréd, 1961, 516, 0143666, 515, tudományos, akadémia, matematikai, kutató, intézetének, közleményei, 109, s0304, 00303, 270, games, fifty, liars, winklmann, 800133, 804351, procedures, kleitman, daniel, albert, 1989, 202, 0304, 90077, 185, ben, hassidim, avinatan, 230, 7695, 3436, 1109, focs, 49th, foundations, bayesian, learner, pretty, good, emamjomeh, zadeh, ehsan, kempe, david, singhal, vikrant, 48th, 532, 2897518, 2897656, 1503, 00805, 519, deterministic, 2004, 284, 0022, 0000, 003, 269, 33rd, 329, 58113, 349, 380752, 380818, 322, perl, yehoshua, itai, alon, avni, haim, 1978, 553, 11089655, 359545, 359557, 550, important, burton, 1970, trade, offs, allowable, 426, 7931252, 362686, 362692, 422, fan, bin, andersen, dave, kaminsky, mitzenmacher, 2014, international, emerging, networking, experiments, technologies, 2674005, 2674994, practically, silverstein, alan, hewlett, packard, shop, bitwise, dietzfelbinger, martin, auf, der, heide, friedhelm, rohnert, hans, 1994, perfect, 761, 1137, s0097539791194094, 738, siam, tarjan, mehlhorn, kurt, karlin, anna, multiway, drums, exercises, beame, 1006, 1822, fich, faith, sequential, allocation, pathological, virak, layouts, 3053370, 1509, 05053, experimental, algorithmics, relevant, quotations, ieee, 754, pun, explanation, github, total_cmp, f32, f64, golddranks, pull, request, 72568, lang, herf, december, stereopsis, graphics, radix, rolfe, timothy, 289251, 289255, signum, newsletter, analytic, 169, theorem, 461, 463, selection, bibliography, described, 214, titled, program, 13406983, 0004, 5411, 321119, 321120, 161, flores, ivan, madpis, george, 603, 43325465, 0001, 0782, 362663, 362752, 602, dense, mathworld, weisstein, eric, williams, louis, 1976, 14th, southeast, 101, 503561, 503582, modification, improvements, exploits, gain, advantages, setting, affect, guaranteed, inserting, alternating, pattern, maximizes, formal, minimal, quickly, outgrows, outperforms, 75n, showed, compared, solely, let, minimize, turns, proved, already, consecutive, equivalently, halves, interior, matter, div, anthony, lin, q81434400, 2470, 6345, 15347, wjs, 005, updated, reintegrated, reviewer, reports, submitted, calculation, multiplicative, equations, zero, partition_point, binary_search_by_key, binary_search_by, includes, without, having, cfarraybsearchvalues, core, usingcomparator, options, insortedrange, indexofobject, cocoa, objective, versions, generic, net, overloaded, slices, searchstrings, searchfloat64s, searchints, verb, phobos, default, offer, trisect, lowerbound, equalrange, assumesorted, sortedrange, equal_range, upper_bound, lower_bound, typically, official, include, routines, libraries, infinite, occur, correctly, exceeds, convey, exited, moved, place, who, incorrectly, defining, fixed, span, calculated, exceed, nonnegative, avoided, arithmetic, assigned, ninety, percent, provide, hours, working, mainly, answer, rare, study, shows, accurate, five, textbooks, remained, undetected, had, bug, nine, basic, comparatively, details, surprisingly, tricky, 1946, mention, seminal, foundational, presented, placed, reducing, chandra, introduced, stanford, equality, henry, moore, school, lectures, john, mauchly, items, allow, antiquity, earliest, inakibit, anu, babylon, dating, 500, entry, easier, letter, discovered, latin, finished, 1286, describe, rules, words, alphabetical, opposed, just, catholicon, aegean, islands, lexicographical, reciprocals, sexagesimal, 200, bce, proportion, providing, unordered, sqrt, natural, reliably, controls, reliability, yielded, variant, questions, ulam, game, entropy, upon, querying, incident, shortest, unequal, originally, various, elsewhere, routing, internet, protocol, mining, separately, reduces, storing, practice, compensates, estimated, distribution, estimates, basis, guess, needed, estimate, specify, estimating, starts, afterwards, sets, switches, before, started, becomes, improvement, lies, beginning, subsequent, containing, differences, computed, differ, amount, reduce, subtracts, calculate, decimal, advantage, properties, thus, consuming, lack, combination, approaches, mitigate, retaining, tries, fusion, van, emde, boas, suffer, false, positives, suited, simplest, limited, compactly, requiring, judy1, handles, implementing, maps, generally, ideal, them, supports, amortized, lend, hard, structured, generalizes, frequently, organize, term, databases, imperfectly, balance, rarely, produce, severely, imbalanced, approaching, principle, arranged, retain, allows, needs, unsorted, merge, quicksort, interleaved, retrieval, operation, complicate, especially, inserted, noted, 512, kib, tends, cause, how, requested, tend, causing, collisions, aliasing, fetch, meaning, handle, addresses, hitting, happens, setup, manage, areas, affected, prevented, offsetting, split, divides, thrashing, addressable, translation, lookaside, buffer, architectures, hardware, separate, processors, recently, sequentially, distant, probing, locality, contributor, leads, despite, dependent, nature, branches, conditional, moves, steel, bank, kind, differently, nan, total, analyzing, increases, double, achieved, significant, digital, checking, cuts, taken, guarantees, maximum, times, slight, compensate, determined, augmenting, fewer, remains, extended, equivalent, specified, connections, passes, through, corresponding, counting, represents, depends, word, exhibit, filled, completely, eliminate, dividing, ensures, subarrays, approximately, denotes, argument, cdot, analyzed, viewing, rest, fashion, starting, traversed, depending, adjusted, down, entries, those, whichever, closer, performs, trivial, extend, operates, seeking, adapted, shown, binary_search_rightmost, binary_search_leftmost, geq, consider, returns, sometimes, necessary, duplicated, exists, binary_search_alternative, neq, alternatively, appears, iterative, track, boundaries, variable, remain, refers, conveys, uses, subroutine, cdots, ldots, begins, particular, solves, fields, able, wider, relative, absent, again, repeating, empty, chop, yes, finite, continuous, redirected, free, encyclopedia, item, wikibooks, projects, printable, download, print, export, switch, legacy, parser, get, shortened, url, permanent, link, actions, talk, tiếng, việt, oʻzbekcha, ўзбекча, українська, türkçe, ไทย, தமிழ், svenska, српски, srpski, shqip, slovenščina, slovenčina, русский, română, português, polski, norsk, bokmål, nederlands, മലയാളം, македонски, 한국어, ಕನ್ನಡ, ქართული, 日本語, italiano, bahasa, indonesia, interlingua, हिन्दी, עברית, français, suomi, فارسی, eesti, español, ελληνικά, deutsch, čeština, català, বাংলা, български, azərbaycanca, الدارجة, العربية, top, personal, special, pages, recent, community, portal, learn, contribute, events, navigation,
Text of the page (random words):
e elements instead of specific bounds uniform binary search stores instead of the lower and upper bounds the difference in the index of the middle element from the current iteration to the next iteration a lookup table containing the differences is computed beforehand for example if the array to be searched is 1 2 3 4 5 6 7 8 9 10 11 the middle element m displaystyle m would be 6 in this case the middle element of the left subarray 1 2 3 4 5 is 3 and the middle element of the right subarray 7 8 9 10 11 is 9 uniform binary search would store the value of 3 as both indices differ from 6 by this same amount 44 to reduce the search space the algorithm either adds or subtracts this change from the index of the middle element uniform binary search may be faster on systems where it is inefficient to calculate the midpoint such as on decimal computers 45 exponential search edit main article exponential search visualization of exponential searching finding the upper bound for the subsequent binary search exponential search extends binary search to unbounded lists it starts by finding the first element with an index that is both a power of two and greater than the target value afterwards it sets that index as the upper bound and switches to binary search a search takes log 2 x 1 textstyle lfloor log _ 2 x 1 rfloor iterations before binary search is started and at most log 2 x textstyle lfloor log _ 2 x rfloor iterations of the binary search where x textstyle x is the position of the target value exponential search works on bounded lists but becomes an improvement over binary search only if the target value lies near the beginning of the array 46 interpolation search edit main article interpolation search visualization of interpolation search using linear interpolation in this case no searching is needed because the estimate of the target s location within the array is correct other implementations may specify another function for estimating the target s location instead of calculating the midpoint interpolation search estimates the position of the target value taking into account the lowest and highest elements in the array as well as length of the array it works on the basis that the midpoint is not the best guess in many cases for example if the target value is close to the highest element in the array it is likely to be located near the end of the array 47 a common interpolation function is linear interpolation if a displaystyle a is the array l r displaystyle l r are the lower and upper bounds respectively and t displaystyle t is the target then the target is estimated to be about t a l a r a l displaystyle t a_ l a_ r a_ l of the way between l displaystyle l and r displaystyle r when linear interpolation is used and the distribution of the array elements is uniform or near uniform interpolation search makes o log log n textstyle o log log n comparisons 47 48 49 in practice interpolation search is slower than binary search for small arrays as interpolation search requires extra computation its time complexity grows more slowly than binary search but this only compensates for the extra computation for large arrays 47 fractional cascading edit main article fractional cascading in fractional cascading each array has pointers to every second element of another array so only one binary search has to be performed to search all the arrays fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays searching each array separately requires o k log n textstyle o k log n time where k textstyle k is the number of arrays fractional cascading reduces this to o k log n textstyle o k log n by storing specific information in each array about each element and its position in the other arrays 50 51 fractional cascading was originally developed to efficiently solve various computational geometry problems fractional cascading has been applied elsewhere such as in data mining and internet protocol routing 50 generalization to graphs edit binary search has been generalized to work on certain types of graphs where the target value is stored in a vertex instead of an array element binary search trees are one such generalization when a vertex node in the tree is queried the algorithm either learns that the vertex is the target or otherwise which subtree the target would be located in however this can be further generalized as follows given an undirected positively weighted graph and a target vertex the algorithm learns upon querying a vertex that it is equal to the target or it is given an incident edge that is on the shortest path from the queried vertex to the target the standard binary search algorithm is simply the case where the graph is a path similarly binary search trees are the case where the edges to the left or right subtrees are given when the queried vertex is unequal to the target for all undirected positively weighted graphs there is an algorithm that finds the target vertex in o log n displaystyle o log n queries in the worst case 52 noisy binary search edit in noisy binary search there is a certain probability that a comparison is incorrect noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array for each pair of elements there is a certain probability that the algorithm makes the wrong comparison noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position every noisy binary search procedure must make at least 1 τ log 2 n h p 10 h p displaystyle 1 tau frac log _ 2 n h p frac 10 h p comparisons on average where h p p log 2 p 1 p log 2 1 p displaystyle h p p log _ 2 p 1 p log _ 2 1 p is the binary entropy function and τ displaystyle tau is the probability that the procedure yields the wrong position 53 54 55 the noisy binary search problem can be considered as a case of the rényi ulam game 56 a variant of twenty questions where the answers may be wrong 57 quantum binary search edit classical computers are bounded to the worst case of exactly log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor iterations when performing binary search quantum algorithms for binary search are still bounded to a proportion of log 2 n textstyle log _ 2 n queries representing iterations of the classical procedure but the constant factor is less than one providing for a lower time complexity on quantum computers any exact quantum binary search procedure that is a procedure that always yields the correct result requires at least 1 π ln n 1 0 22 log 2 n textstyle frac 1 pi ln n 1 approx 0 22 log _ 2 n queries in the worst case where ln textstyle ln is the natural logarithm 58 there is an exact quantum binary search procedure that runs in 4 log 605 n 0 433 log 2 n textstyle 4 log _ 605 n approx 0 433 log _ 2 n queries in the worst case 59 in comparison grover s algorithm is the optimal quantum algorithm for searching an unordered list of elements and it requires o n displaystyle o sqrt n queries 60 history edit the idea of sorting a list of items to allow for faster searching dates back to antiquity the earliest known example was the inakibit anu tablet from babylon dating back to c 200 bce the tablet contained about 500 sexagesimal numbers and their reciprocals sorted in lexicographical order which made searching for a specific entry easier in addition several lists of names that were sorted by their first letter were discovered on the aegean islands catholicon a latin dictionary finished in 1286 ce was the first work to describe rules for sorting words into alphabetical order as opposed to just the first few letters 9 in 1946 john mauchly made the first mention of binary search as part of the moore school lectures a seminal and foundational college course in computing 9 in 1957 william wesley peterson published the first method for interpolation search 9 61 every published binary search algorithm worked only for arrays whose length is one less than a power of two i until 1960 when derrick henry lehmer published a binary search algorithm that worked on all arrays 63 in 1962 hermann bottenbruch presented an algol 60 implementation of binary search that placed the comparison for equality at the end increasing the average number of iterations by one but reducing to one the number of comparisons per iteration 8 the uniform binary search was developed by a k chandra of stanford university in 1971 9 in 1986 bernard chazelle and leonidas j guibas introduced fractional cascading as a method to solve numerous search problems in computational geometry 50 64 65 implementation issues edit although the basic idea of binary search is comparatively straightforward the details can be surprisingly tricky donald knuth 2 when jon bentley assigned binary search as a problem in a course for professional programmers he found that ninety percent failed to provide a correct solution after several hours of working on it mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases 66 a study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks 67 furthermore bentley s own implementation of binary search published in his 1986 book programming pearls contained an overflow error that remained undetected for over twenty years the java programming language library implementation of binary search had the same overflow bug for more than nine years 68 in a practical implementation the variables used to represent the indices will often be of fixed size integers and this can result in an arithmetic overflow for very large arrays if the midpoint of the span is calculated as l r 2 displaystyle frac l r 2 then the value of l r displaystyle l r may exceed the range of integers of the data type used to store the midpoint even if l displaystyle l and r displaystyle r are within the range if l displaystyle l and r displaystyle r are nonnegative this can be avoided by calculating the midpoint as l r l 2 displaystyle l frac r l 2 69 an infinite loop may occur if the exit conditions for the loop are not defined correctly once l displaystyle l exceeds r displaystyle r the search has failed and must convey the failure of the search in addition the loop must be exited when the target element is found or in the case of an implementation where this check is moved to the end checks for whether the search was successful or failed at the end must be in place bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions 8 70 library support edit many languages standard libraries include binary search routines c provides the function bsearch in its standard library which is typically implemented via binary search although the official standard does not require it to do so 71 c s standard library provides the functions binary_search lower_bound upper_bound and equal_range 72 using the c 20 std ranges library it can be applied over a range as std ranges binary_search d s standard library phobos in std range module provides a type sortedrange returned by sort and assumesorted functions with methods contains equalrange lowerbound and trisect that use binary search techniques by default for ranges that offer random access 73 cobol provides the search all verb for performing binary searches on cobol ordered tables 74 go s sort standard library package contains the functions search searchints searchfloat64s and searchstrings which implement general binary search as well as specific implementations for searching slices of integers floating point numbers and strings respectively 75 java offers a set of overloaded binarysearch static methods in the classes arrays and collections in the standard java util package for performing binary searches on java arrays and on list s respectively 76 77 microsoft s net framework 2 0 offers static generic versions of the binary search algorithm in its collection base classes an example would be system array s method binarysearch t t array t value 78 for objective c the cocoa framework provides the nsarray indexofobject insortedrange options usingcomparator method in mac os x 10 6 79 apple s core foundation c framework also contains a cfarraybsearchvalues function 80 python provides the bisect module that keeps a list in sorted order without having to sort the list after each insertion 81 ruby s array class includes a bsearch method with built in approximate matching 82 rust s slice primitive provides binary_search binary_search_by binary_search_by_key and partition_point 83 see also edit bisection method algorithm for finding a zero of a function the same idea used to solve equations in the real numbers multiplicative binary search binary search variation with simplified midpoint calculation notes and references edit this article was submitted to wikijournal of science for external academic peer review in 2018 reviewer reports the updated content was reintegrated into the wikipedia page under a cc by sa 3 0 license 2019 the version of record as reviewed is anthony lin et al 2 july 2019 binary search algorithm pdf wikijournal of science 2 1 5 doi 10 15347 wjs 2019 005 issn 2470 6345 wikidata q81434400 notes edit the o displaystyle o is big o notation and log displaystyle log is the logarithm in big o notation the base of the logarithm does not matter since every logarithm of a given base is a constant factor of another logarithm of another base that is log b n log k n log k b displaystyle log _ b n log _ k n div log _ k b where log k b displaystyle log _ k b is a constant any search algorithm based solely on comparisons can be represented using a binary comparison tree an internal path is any path from the root to an existing node let i displaystyle i be the internal path length the sum of the lengths of all internal paths if each element is equally likely to be searched the average case is 1 i n displaystyle 1 frac i n or simply one plus the average of all the internal path lengths of the tree this is because internal paths represent the elements that the search algorithm compares to the target the lengths of these internal paths represent the number of iterations after the root node adding the average of these lengths to the one iteration at the root yields the average case therefore to minimize the average number of comparisons the internal path length i displaystyle i must be minimized it turns out that the tree for binary search minimizes the internal path length knuth 1998 proved that the external path length the path length over all nodes where both children are present for each already existing node is minimized when the external nodes the nodes with no children lie within two consecutive levels of the tree this also applies to internal paths as internal path length i displaystyle i is linearly related to external path length e displaystyle...
|
