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):
ven an array a displaystyle a of n displaystyle n elements with values or records a 0 a 1 a 2 a n 1 displaystyle a_ 0 a_ 1 a_ 2 ldots a_ n 1 sorted such that a 0 a 1 a 2 a n 1 displaystyle a_ 0 leq a_ 1 leq a_ 2 leq cdots leq a_ n 1 and target value t displaystyle t the following subroutine uses binary search to find the index of t displaystyle t in a displaystyle a 7 set l displaystyle l to 0 displaystyle 0 and r displaystyle r to n 1 displaystyle n 1 if l r displaystyle l r the search terminates as unsuccessful set m displaystyle m the position of the middle element to l displaystyle l plus the floor of r l 2 displaystyle frac r l 2 which is the greatest integer less than or equal to r l 2 displaystyle frac r l 2 if a m t displaystyle a_ m t set l displaystyle l to m 1 displaystyle m 1 and go to step 2 if a m t displaystyle a_ m t set r displaystyle r to m 1 displaystyle m 1 and go to step 2 now a m t displaystyle a_ m t the search is done return m displaystyle m this iterative procedure keeps track of the search boundaries with the two variables l displaystyle l and r displaystyle r the procedure may be expressed in pseudocode as follows where the variable names and types remain the same as above floor is the floor function and unsuccessful refers to a specific value that conveys the failure of the search 7 binary search function binary_search a n t is l 0 r n 1 while l r do m l floor r l 2 if a m t then l m 1 else if a m t then r m 1 else return m return unsuccessful alternatively the algorithm may take the ceiling of r l 2 displaystyle frac r l 2 this may change the result if the target value appears more than once in the array alternative procedure edit in the above procedure the algorithm checks whether the middle element m displaystyle m is equal to the target t displaystyle t in every iteration some implementations leave out this check during each iteration the algorithm would perform this check only when one element is left when l r displaystyle l r this results in a faster comparison loop as one comparison is eliminated per iteration while it requires only one more iteration on average 8 hermann bottenbruch published the first implementation to leave out this check in 1962 8 9 set l displaystyle l to 0 displaystyle 0 and r displaystyle r to n 1 displaystyle n 1 while l r displaystyle l neq r set m displaystyle m the position of the middle element to l displaystyle l plus the ceiling of r l 2 displaystyle frac r l 2 which is the least integer greater than or equal to r l 2 displaystyle frac r l 2 if a m t displaystyle a_ m t set r displaystyle r to m 1 displaystyle m 1 else a m t displaystyle a_ m leq t set l displaystyle l to m displaystyle m now l r displaystyle l r the search is done if a l t displaystyle a_ l t return l displaystyle l otherwise the search terminates as unsuccessful where ceil is the ceiling function the pseudocode for this version is function binary_search_alternative a n t is l 0 r n 1 while l r do m l ceil r l 2 if a m t then r m 1 else l m if a l t then return l return unsuccessful duplicate elements edit the procedure may return any index whose element is equal to the target value even if there are duplicate elements in the array for example if the array to be searched was 1 2 3 4 4 5 6 7 displaystyle 1 2 3 4 4 5 6 7 and the target was 4 displaystyle 4 then it would be correct for the algorithm to either return the 4th index 3 or 5th index 4 element the regular procedure would return the 4th element index 3 in this case it does not always return the first duplicate consider 1 2 4 4 4 5 6 7 displaystyle 1 2 4 4 4 5 6 7 which still returns the 4th element however it is sometimes necessary to find the leftmost element or the rightmost element for a target value that is duplicated in the array in the above example the 4th element is the leftmost element of the value 4 while the 5th element is the rightmost element of the value 4 the alternative procedure above will always return the index of the rightmost element if such an element exists 9 procedure for finding the leftmost element edit to find the leftmost element the following procedure can be used 10 set l displaystyle l to 0 displaystyle 0 and r displaystyle r to n displaystyle n while l r displaystyle l r set m displaystyle m the position of the middle element to l displaystyle l plus the floor of r l 2 displaystyle frac r l 2 which is the greatest integer less than or equal to r l 2 displaystyle frac r l 2 if a m t displaystyle a_ m t set l displaystyle l to m 1 displaystyle m 1 else a m t displaystyle a_ m geq t set r displaystyle r to m displaystyle m return l displaystyle l if l n displaystyle l n and a l t displaystyle a_ l t then a l displaystyle a_ l is the leftmost element that equals t displaystyle t even if t displaystyle t is not in the array l displaystyle l is the rank of t displaystyle t in the array or the number of elements in the array that are less than t displaystyle t where floor is the floor function the pseudocode for this version is function binary_search_leftmost a n t l 0 r n while l r m l floor r l 2 if a m t l m 1 else r m return l procedure for finding the rightmost element edit to find the rightmost element the following procedure can be used 10 set l displaystyle l to 0 displaystyle 0 and r displaystyle r to n displaystyle n while l r displaystyle l r set m displaystyle m the position of the middle element to l displaystyle l plus the floor of r l 2 displaystyle frac r l 2 which is the greatest integer less than or equal to r l 2 displaystyle frac r l 2 if a m t displaystyle a_ m t set r displaystyle r to m displaystyle m else a m t displaystyle a_ m leq t set l displaystyle l to m 1 displaystyle m 1 return r 1 displaystyle r 1 if r 0 displaystyle r 0 and a r 1 t displaystyle a_ r 1 t then a r 1 displaystyle a_ r 1 is the rightmost element that equals t displaystyle t even if t displaystyle t is not in the array n r displaystyle n r is the number of elements in the array that are greater than t displaystyle t where floor is the floor function the pseudocode for this version is function binary_search_rightmost a n t l 0 r n while l r m l floor r l 2 if a m t r m else l m 1 return r 1 approximate matches edit binary search can be adapted to compute approximate matches in the example above the rank predecessor successor and nearest neighbor are shown for the target value 5 displaystyle 5 which is not in the array the above procedure only performs exact matches finding the position of a target value however it is trivial to extend binary search to perform approximate matches because binary search operates on sorted arrays for example binary search can be used to compute for a given value its rank the number of smaller elements predecessor next smallest element successor next largest element and nearest neighbor range queries seeking the number of elements between two values can be performed with two rank queries 11 rank queries can be performed with the procedure for finding the leftmost element the number of elements less than the target value is returned by the procedure 11 predecessor queries can be performed with rank queries if the rank of the target value is r displaystyle r its predecessor is r 1 displaystyle r 1 12 for successor queries the procedure for finding the rightmost element can be used if the result of running the procedure for the target value is r displaystyle r then the successor of the target value is r 1 displaystyle r 1 12 the nearest neighbor of the target value is either its predecessor or successor whichever is closer range queries are also straightforward 12 once the ranks of the two values are known the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks this count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains entries matching those endpoints 13 performance edit a tree representing binary search the array being searched here is 20 30 40 50 80 90 100 displaystyle 20 30 40 50 80 90 100 and the target value is 40 displaystyle 40 the worst case is reached when the search reaches the deepest level of the tree while the best case is reached when the target value is the middle element in terms of the number of comparisons the performance of binary search can be analyzed by viewing the run of the procedure on a binary tree the root node of the tree is the middle element of the array the middle element of the lower half is the left child node of the root and the middle element of the upper half is the right child node of the root the rest of the tree is built in a similar fashion starting from the root node the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration 6 14 in the worst case binary search makes log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor iterations of the comparison loop where the textstyle lfloor cdot rfloor notation denotes the floor function that yields the greatest integer less than or equal to the argument and log 2 textstyle log _ 2 is the binary logarithm this is because the worst case is reached when the search reaches the deepest level of the tree and there are always log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor levels in the tree for any binary search the worst case may also be reached when the target element is not in the array if n textstyle n is one less than a power of two then this is always the case otherwise the search may perform log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor iterations if the search reaches the deepest level of the tree however it may make log 2 n textstyle lfloor log _ 2 n rfloor iterations which is one less than the worst case if the search ends at the second deepest level of the tree 15 on average assuming that each element is equally likely to be searched binary search makes log 2 n 1 2 log 2 n 1 log 2 n 2 n displaystyle lfloor log _ 2 n rfloor 1 2 lfloor log _ 2 n rfloor 1 lfloor log _ 2 n rfloor 2 n iterations when the target element is in the array this is approximately equal to log 2 n 1 displaystyle log _ 2 n 1 iterations when the target element is not in the array binary search makes log 2 n 2 2 log 2 n 1 n 1 displaystyle lfloor log _ 2 n rfloor 2 2 lfloor log _ 2 n rfloor 1 n 1 iterations on average assuming that the range between and outside elements is equally likely to be searched 14 in the best case where the target value is the middle element of the array its position is returned after one iteration 16 in terms of iterations no search algorithm that works only by comparing elements can exhibit better average and worst case performance than binary search the comparison tree representing binary search has the fewest levels possible as every level above the lowest level of the tree is filled completely b otherwise the search algorithm can eliminate few elements in an iteration increasing the number of iterations required in the average and worst case this is the case for other search algorithms based on comparisons as while they may work faster on some target values the average performance over all elements is worse than binary search by dividing the array in half binary search ensures that the size of both subarrays are as similar as possible 14 space complexity edit binary search requires three pointers to elements which may be array indices or pointers to memory locations regardless of the size of the array therefore the space complexity of binary search is o 1 displaystyle o 1 in the word ram model of computation derivation of average case edit the average number of iterations performed by binary search depends on the probability of each element being searched the average case is different for successful searches and unsuccessful searches it will be assumed that each element is equally likely to be searched for successful searches for unsuccessful searches it will be assumed that the intervals between and outside elements are equally likely to be searched the average case for successful searches is the number of iterations required to search every element exactly once divided by n displaystyle n the number of elements the average case for unsuccessful searches is the number of iterations required to search an element within every interval exactly once divided by the n 1 displaystyle n 1 intervals 14 successful searches edit in the binary tree representation a successful search can be represented by a path from the root to the target node called an internal path the length of a path is the number of edges connections between nodes that the path passes through the number of iterations performed by a search given that the corresponding path has length l is l 1 displaystyle l 1 counting the initial iteration the internal path length is the sum of the lengths of all unique internal paths since there is only one path from the root to any single node each internal path represents a search for a specific element if there are n elements which is a positive integer and the internal path length is i n displaystyle i n then the average number of iterations for a successful search t n 1 i n n displaystyle t n 1 frac i n n with the one iteration added to count the initial iteration 14 since binary search is the optimal algorithm for searching with comparisons this problem is reduced to calculating the minimum internal path length of all binary trees with n nodes which is equal to 17 i n k 1 n log 2 k displaystyle i n sum _ k 1 n left lfloor log _ 2 k right rfloor for example in a 7 element array the root requires one iteration the two elements below the root require two iterations and the four elements below require three iterations in this case the internal path length is 17 k 1 7 log 2 k 0 2 1 4 2 2 8 10 displaystyle sum _ k 1 7 left lfloor log _ 2 k right rfloor 0 2 1 4 2 2 8 10 the average number of iterations would be 1 10 7 2 3 7 displaystyle 1 frac 10 7 2 frac 3 7 based on the equation for the average case the sum for i n displaystyle i n can be simplified to 14 i n k 1 n log 2 k n 1 log 2 n 1 2 log 2 n 1 1 2 displaystyle i n sum _ k 1 n left lfloor log _ 2 k right rfloor n 1 left lfloor log _ 2 n 1 right rfloor 2 left lfloor log _ 2 n 1 right rfloor 1 2 substituting the equation for i n displaystyle i n into the equation for t n displaystyle t n 14 t n 1 n 1 log 2 n 1 2 log 2 n 1 1 2 n log 2 n 1 2 log 2 n 1 log 2 n 2 n displaystyle t n 1 frac n 1 left lfloor log _ 2 n 1 right rfloor 2 left lfloor log _ 2 n 1 right rfloor 1 2 n lfloor log _ 2 n rfloor 1 2 lfloor log _ 2 n rfloor 1 lfloor log _ 2 n rfloor 2 n for integer n this is equivalent to the equation for the average case on a successful search specified above unsuccessful searches edit unsuccessful searches can be represented by augmenting the tree with external nodes which forms an extended binary tree if an internal ...
|
