text:
Death Wish (2018 film)
From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Death Wish
Theatrical release poster
Directed by
Eli Roth
Produced by
Roger Birnbaum
Screenplay by
Joe Carnahan
Based on
Death Wish
by Wendell Mayes
Death Wish
by Brian Garfield
Starring
Bruce Willis
Vincent D'Onofrio
Elisabeth Shue
Dean Norris
Kimberly Elise
Music by
Ludwig Göransson
Cinematography
Rogier Stoffers
Edited by
Mark Goldblatt
Production
companies
Cave 76 Productions[1]
MGM Studios[1]
Distributed by
Metro-Goldwyn-Mayer
Release date
March 2, 2018 (2018-03-02)
Running time
107 minutes[2]
Country
United States
Language
English
Budget
$30 million[2]
Box office
$48.6 million[2]
Death Wish is a 2018 American vigilante action thriller film directed by Eli Roth and written by Joe Carnahan. It is the sixth installment of the Death Wish series and a remake of the 1974 film of the same name starring Charles Bronson, based on Brian Garfield's 1972 novel. The film stars Bruce Willis as Paul Kersey, a Chicago doctor who sets out to get revenge on the men who attacked his family. Vincent D'Onofrio, Elisabeth Shue, Dean Norris, and Kimberly Elise also star.
The film was released in the United States by Metro-Goldwyn-Mayer and in international markets by Annapurna Pictures on March 2, 2018. It received generally negative reviews, with criticism aimed at it for not adding anything new to previous installments.
Contents
[hide]
1 Plot
2 Cast
3 Production
3.1 Development
3.2 Filming
4 Release
5 Reception
5.1 Box office
5.2 Critical response
6 See also
7 References
8 External links
Plot[edit]
Paul Kersey, who lives with his wife Lucy and college-bound daughter Jordan, works as a trauma surgeon at a Chicago hospital. After having lunch at a restaurant, Paul gives the keys to his car to a valet, Miguel, who secretly takes a picture of their home address from the car's navigation software after overhearing when they will all be out one night. Later, while Paul is working late at the hospital, three masked men invade the Kersey's home. Jordan and Lucy return home and are both shot and Paul learns at the hospital that Lucy died and Jordan fell into a coma.
Police Detective Kevin Raines is tasked with the case, but Paul soon becomes frustrated with the lack of progress in the investigation. One night, Paul comes across two thugs harassing a woman and intervenes and gets beaten. Paul then visits a gun store, but when he sees he's being videotaped, he decides to leave without purchasing anything. When an injured gang member is brought in to the hospital and his Glock 17 falls from the gurney, Paul steals the weapon and then uses online videos to learn how to maintain and use it. Eventually, Paul uses it to stop a carjacking, a video of which goes viral; Paul is dubbed Chicago's "Grim Reaper". When an unconscious Miguel is hospitalized, Paul recognizes his stolen watch around his wrist. After Miguel dies, Paul takes Miguel's phone and discovers a photograph and a text on it suggesting that a liquor store is where the thieves bring and re-sell their stolen goods.
Paul visits the liquor store, but the owner, Ponytail, realizes who he is, secretly messages an accomplice for backup and reaches for a gun. Paul stabs him with a dart and demands the goods stolen from his house. Ponytail's accomplice, Fish, arrives and accidentally kills Ponytail. After shooting Fish, Paul learns from him that Lucy's killer is an auto body shop worker named Joe. Fish kicks Paul and gains the upper hand, but is stunned by a falling bowling ball, allowing Paul to kill him. At the auto body shop, Paul ambushes Joe while he is working under a car. He tortures Joe for information by cutting his sciatic nerve with a scalpel and pouring brake fluid into the wound. Joe divulges that their leader, Knox, shot Lucy. Paul then removes the jack holding the car up, causing it to crush Joe's head.
Paul receives a phone call from Knox, telling him to meet him in a bathroom at a nightclub. When he arrives, Paul calls the number back and hears it ringing in one of the stalls. He shoots through the stall door, only to find that it was a ruse. Knox opens fire from the other end of the bathroom and the two engage in a shootout, injuring both before both escape. After going home and encountering his brother, Frank, Paul is informed from the hospital that Jordan has regained consciousness. A week later, as Paul brings Jordan home from the hospital, Knox talks to both of them in the hospital elevator: Jordan does not recognize Knox, but Knox tells Paul he'll see him around. Paul returns to the gun store to legally purchase weapons to legally defend his remaining family.
Sometime later, Knox and two other thugs prepare to invade Paul's home at night. Paul glimpses a man running across his lawn and hides Jordan in a closet under the stairs, telling her to call the police. After killing the two thugs in the upstairs bedroom, Paul heads into the basement, where he suspects Knox is located. There, Knox emerges from the darkness, shoots Paul in the shoulder and threatens to burn Jordan alive. When Knox is distracted by Jordan yelling out her father's name, Paul retrieves a fully automatic M4 carbine assault rifle from a hidden compartment under a coffee table and shoots Knox dead. When the police arrive, Detective Raines suspects that Paul is the "Grim Reaper", but pretends to buy his story because he's satisfied that justice was served and because Paul subtly informs him that his "Grim Reaper" days are over.
Months later, Paul drops Jordan off at NYU. As Paul is leaving, he spots a man who steals a bag from a bellhop, calls out to him and points at him with a finger gun.
Cast[edit]
Bruce Willis as Dr. Paul Kersey, Jordan’s father, Lucy’s husband and Frank’s brother, a Chicago-based doctor turned vigilante
Vincent D'Onofrio as Frank Kersey, Paul Kersey’s brother
Dean Norris as Detective Kevin Raines, the main detective in charge of Lucy's murder investigation and Detective Leonore Jackson’s partner
Kimberly Elise as Detective Leonore Jackson, partner to Detective Kevin Raines and one of the detectives leading the investigation of Lucy's murder investigation.
Mike Epps as Dr. Chris Salgado, a playboy doctor and close friend of Paul Kersey
Elisabeth Shue as Lucy Rose Kersey, the wife of Paul Kersey and Jordan’s mother
Camila Morrone as Jordan Kersey, the daughter of Paul and Lucy
Ronnie Gene Blevins as Joe, a mechanic and Knox's partner-in-crime
Beau Knapp as Knox, the criminal in charge of Joe and Fish
Jack Kesy as Tate "Fish" Karp, Knox's partner-in-crime
Wendy Crewson as Dr. Jill Klavens, a psychiatrist
Kirby Bliss Blanton as Bethany, the spokesperson of the gun shop Kersey visits.
Len Cariou as Ben, Lucy's father
Luis Oliva as Miguel
Troy Kivisto as a FBI Agent
Production[edit]
Development[edit]
Development of the film began in 2006, when Sylvester Stallone announced that he would be directing and starring in a remake of Death Wish (1974). Stallone told Ain't It Cool News, "Instead of the Charles Bronson character being an architect, my version would have him as a very good cop who had incredible success without ever using his gun. So when the attack on his family happens, he's really thrown into a moral dilemma in proceeding to carry out his revenge." He later told the publication that he was no longer involved.[3][4] In a 2009 interview with MTV, though, Stallone stated that he was again considering the project.[5]
In late January 2012, The Hollywood Reporter confirmed that a remake would be written and directed by Joe Carnahan.[6] The film was originally set to star Liam Neeson and Frank Grillo. Carnahan, however, left the project in February 2013 due to creative differences,[7] but received sole writing credit for the completed film.[8] He was replaced as director with Gerardo Naranjo, who was interested in casting Benicio Del Toro in the lead role; this version also never came to fruition.[7]
In March 2016, Paramount Pictures and Metro-Goldwyn-Mayer announced that Aharon Keshales and Navot Papushado would direct with Bruce Willis starring.[9] Willis was chosen from a shortlist which included Russell Crowe, Matt Damon, Will Smith, and Brad Pitt. In May, Keshales and Papushado quit the project after MGM declined to allow them to rewrite Joe Carnahan's original script, which had been approved by Willis.[10] In June, Eli Roth signed on to direct, with the script being rewritten by Scott Alexander and Larry Karaszewski.[11] On August 25, 2016, Vincent D'Onofrio was cast alongside Bruce Willis to play Paul Kersey's brother, Breaking Bad actor Dean Norris also joined Willis in the film.[12] On October 7, 2016, Kimberly Elise and Camila Morrone were cast in the film to play Detective Jackson and Jordan Kersey.[13] Later on October 17, 2016, Ronnie Gene Blevins was cast in the film.[14]
Filming[edit]
Principal photography on the film began in late September 2016 in Chicago, Illinois.[15] Later in October 2016, it began filming in Montreal, Quebec, Canada.[16]
Release[edit]
In June 2017, it was announced Annapurna Pictures would distribute the film on behalf of Metro-Goldwyn-Mayer and release it on November 22, 2017.[17] However in October of 2017, it was announced it was being delayed until March 2, 2018 and that Metro-Goldwyn-Mayer would handle the film's distribution in the United States, while Annapurna Pictures handle its international distribution.[18] It was speculated the delay was due in-part to the mass shooting in Las Vegas several days prior.[19] Death Wish was released theatrically in the United Kingdom on April 6 by Vertigo Releasing. It became available on DVD and BluRay on June 5, 2018.
Reception[edit]
Box office[edit]
As of July 5, 2018, Death Wish has grossed $34 million in the United States and Canada, and $14.5 million in other territories, for a worldwide total of $48.5 million, against a production budget of $30 million.[2]
In the United States and Canada, Death Wish was released alongside Red Sparrow, and was projected to gross $10–20 million from 2,847 theaters in its opening weekend.[20] It made $4.2 million on its first day (including $650,000 from Thursday night previews) and $13 million in its opening weekend, finishing third behind Black Panther ($66.7 million in its third week) and Red Sparrow ($17 million). 55% of its audience was male, while 89% was over the age of 25.[21] It dropped 49% to $6.6 million in its second weekend, finishing at 7th.[22]
Critical response[edit]
"I wanted to really make it about family, and stick to the central issue of what would you do if this happened to your family. The movie for me really is about family and protecting your family and what do you do when you can't get justice for your family? It's not pro-gun. What I really try to do more than anything is show it how it really is, and leave it for the audience to decide."
— Eli Roth on the reception of Death Wish[23]
On review aggregator website Rotten Tomatoes, the film holds an approval rating of 18% based on 129 reviews, and an average rating of 3.9/10. The website's critical consensus reads, "Death Wish is little more than a rote retelling that lacks the grit and conviction of the original — and also suffers from spectacularly bad timing."[24] On Metacritic, the film has a weighted average score of 32 out of 100, based on 30 critics, indicating "generally unfavorable reviews".[25] Audiences polled by CinemaScore gave the film an average grade of "B+" on an A+ to F scale.[21]
The Chicago Sun-Times's Richard Roeper gave the film 2 out of 4 stars, writing, "Even with the social commentary, Death Wish isn’t trying to be some intense, gritty, ripped-from-the-headlines docudrama... A number of gruesome scenes are staged like something out of one of those Final Destination movies, with a bowling ball, a dart, a wrench and other conveniently handy items used as weapons of singular destruction. It’s essentially revenge porn."[26] Michael Phillips of the Chicago Tribune gave the film 1 out of 4 stars and said, "For a while, director Roth plays this stuff relatively straight, and Willis periodically reminds us he can act (the grieving Kersey cries a fair bit here). The script contains a reference to AR-15 rifles; by the end, Willis goes full Willis when his adversaries return to the sanctity of the family home."[19]
Many critics noted the timing of the film's release, coming less than three weeks after the Stoneman Douglas High School shooting in Parkland, Florida.[27] Jeannette Catsoulis of The New York Times called the film "imbecilic", and criticized the film for its jokey tone and "morally unconflicted" approach to its subject matter.[28] Similarly, The Guardian's Amy Nicholson criticized the film for "[flatlining] the politics and [saturating] the pathos", and for insulting both sides of the gun control argument.[29] The Hollywood Reporter's John DeFore noted that the film does not attempt to "use genre metaphors to address real national debates", making the original film "look philosophical by comparison", and he also noted the improbable and contrived nature of Kersey's mission.[30] Writing for the Los Angeles Times, Justin Chang called the film "a slick, straightforward revenge thriller as well as a sham provocation, pandering shamelessly to the viewer's bloodlust while trying to pass as self-aware satire". Chang compared the film unfavorably to the 2007 Death Sentence, citing the lack of consequences that Kersey faces.[31]
Some reviewers stood in defense of the film. Peter Howell of the Toronto Star stated that "Roth and Carnahan do an OK job updating Death Wish", and that the film accurately depicts the "casual way that Americans acquire and use guns". He felt, though, that Liam Neeson would have been a better choice for the lead role.[32] Matthew Rozsa of Salon agreed that the film's release was indeed timed poorly, but argued that "mass shootings have been ubiquitous for so long that I doubt there ever would have been an appropriate release date for a vigilante fantasy. ... It exists everywhere in our culture, from movies and video games to the right-wing talking points that regularly thwart gun control legislation." Rosza considers Death Wish his guilty pleasure, recommending it as a "success" as well as "a competent popcorn muncher that moves at a brisk pace, is about as engaging as your average Law and Order episode and contains an appropriately glowering (if somewhat bored looking) Bruce Willis."[27] The San Francisco Chronicle's Mick Lasalle summed up his review by calling it "way better than all the “Death Wish” sequels" and "easily the second best “Death Wish” movie ever made, and not a distant second."[33]
See also[edit]
Death Wish film series
References[edit]
^ Jump up to: a b "Filmed in Quebec". The Quebec Film and Television Council. Retrieved March 31, 2018.
^ Jump up to: a b c d "Death Wish (2018) - Financial Information". The Numbers. Retrieved 8 July 2018.
Jump up ^ Morris, Clint (June 8, 2008). "Stallone in Death Wish remake? Updated!". Moviehole. Archived from the original on July 3, 2007. Retrieved December 20, 2006. Upon listening to the talkback responses on AICN, many who turned their nose at the idea of a remake, Stallone tells the site today that he will NOT be doing the movie. Yep, he listened to the fans!
Jump up ^ Staff and agencies (November 5, 2007). "Stallone tapped for Death Wish remake". The Guardian. Guardian News and Media. Retrieved November 5, 2007.
Jump up ^ Rosenberg, Adam (October 2, 2009). "Sylvester Stallone Speaks on a 'Death Wish' Remake and Edgar Allen Poe". MTV News. MTV. Retrieved February 21, 2018.
Jump up ^ Gilchrist, Todd (January 31, 2012). "'The Grey' Director Joe Carnahan to Remake 'Death Wish'". The Hollywood Reporter. Prometheus Global Media. Retrieved October 5, 2012.
^ Jump up to: a b Bentancor, Nestor. "Exclusive Benicio Del Toro Rejected to Star in Death Wish Remake 1". Desde Hollywood. Retrieved February 21, 2018.
Jump up ^ Sprague, Mike (February 20, 2018). "Bruce is Back in Bitchin' New Retro Poster for Eli Roth's Death Wish Remake". Dread Central. Dread Central Media. Retrieved February 26, 2018.
Jump up ^ Fleming, Mike Jr. (March 4, 2016). "'Death Wish' Revamp With Bruce Willis To Be Helmed By 'Big Bad Wolves' Directors Aharon Keshales & Navot Papushado". Deadline Hollywood. Penske Business Media.
Jump up ^ Fleming, Mike Jr. (May 4, 2016). "'Big Bad Wolves' Helmers Aharon Keshales & Navot Papushado Exit Bruce Willis 'Death Wish' Remake". Deadline Hollywood. Penske Business Media. Retrieved February 21, 2018.
Jump up ^ Fleming, Mike Jr. (June 20, 2016). "Eli Roth To Direct Bruce Willis In 'Death Wish' Remake". Deadline Hollywood. Penske Business Media. Retrieved June 20, 2016.
Jump up ^ Busch, Anita; Fleming, Mike Jr. (August 25, 2016). "Vincent D'Onofrio Joins Bruce Willis In Eli Roth-Helmed 'Death Wish'". Deadline Hollywood. Penske Business Media.
Jump up ^ N'Duka, Amanda (October 7, 2016). "Eli Roth's 'Death Wish' Adds Kimberly Elise and Camilla Morrone". Deadline Hollywood. Penske Business Media. Retrieved October 9, 2016.
Jump up ^ N'Duka, Amanda (October 18, 2016). "Thriller 'D.O.A. Blood River' Sets Cast; Ronnie Gene Blevins Joins 'Death Wish'". Deadline Hollywood. Penske Business Media. Retrieved October 18, 2016.
Jump up ^ Metz, Nina (September 26, 2016). "Bruce Willis shooting 'Death Wish' remake in Chicago this week". Chicago Tribune. Retrieved October 9, 2016.
Jump up ^ DailyMail.com Reporter (October 13, 2016). "Hugs and kisses! Bruce Willis, 61, gets close to Eighties icon Elisabeth Shue, 53, on Montreal set of Death Wish reboot". Daily Mail. Associated Newspapers. Retrieved October 18, 2016.
Jump up ^ D'Alessandro, Anthony (June 8, 2017). "Annapurna To Release MGM's 'Death Wish' Over Thanksgiving; Sets October Date For 'Professor Marston & The Wonder Women'". Deadline Hollywood. Penske Business Media. Retrieved June 8, 2017.
Jump up ^ D'Alessandro, Anthony (October 5, 2017). "Eli Roth 'Death Wish' Reboot Springs To March". Deadline Hollywood. Penske Business Media. Retrieved October 7, 2017.
^ Jump up to: a b Philips, Michael (March 1, 2018). "'Death Wish': Bruce Willis makes Chicago bleed all over the place". Chicago Tribune. Retrieved March 1, 2018.
Jump up ^ McNary, Dave (February 20, 2018). "Will 'Black Panther' See One of the Best Second Weekends Ever?". Variety. Penske Business Media. Retrieved February 21, 2018.
^ Jump up to: a b D'Alessandro, Anthony (March 4, 2018). "'Black Panther' Busts Past Half Billion; 'Red Sparrow' Flies Low With $17M – Sunday AM B.O. Update". Deadline Hollywood. Penske Business Media. Retrieved March 4, 2018.
Jump up ^ D'Alessandro, Anthony (March 11, 2018). "'Black Panther' Rules 4th Frame With $41M+; 'A Wrinkle In Time' At $33M+: A Diversity & Disney Dominant Weekend". Deadline Hollywood. Penske Business Media. Retrieved March 16, 2018.
Jump up ^ Schwartz, Dana (March 5, 2018). "Death Wish director Eli Roth responds to critics of controversial remake". Entertainment Weekly. Time. Retrieved March 6, 2018.
Jump up ^ "Death Wish (2018)". Rotten Tomatoes. Fandango Media. Retrieved April 19, 2018.
Jump up ^ "Death Wish Reviews". Metacritic. CBS Interactive. Retrieved March 16, 2018.
Jump up ^ Roeper, Richard (March 1, 2018). "Little seems real — not Chicago, not bloodshed — in Bruce Willis' 'Death Wish'". Chicago Sun Times. Retrieved March 1, 2018.
^ Jump up to: a b Rosza, Matthew (March 3, 2018). "Is the "Death Wish" remake as disgustingly right-wing as the original series?". Salon. Salon Media Group. Retrieved March 3, 2018.
Jump up ^ Catsoulis, Jeannette (March 1, 2018). "Review: Cleaning Up Chicago in 'Death Wish'". The New York Times. The New York Times Company. Retrieved March 1, 2018.
Jump up ^ Nicholson, Amy (March 1, 2018). "Death Wish review – Bruce Willis stacks up corpses in gutless remake". The Guardian. Guardian Media Group. Retrieved March 1, 2018.
Jump up ^ DeFore, John (March 1, 2018). "'Death Wish': Film Review". The Hollywood Reporter. Retrieved March 1, 2018.
Jump up ^ Chang, Justin (March 1, 2018). "Bruce Willis takes aim and misfires in an imbecilic 'Death Wish' remake". Los Angeles Times. Retrieved March 2, 2018.
Jump up ^ Howell, Peter (March 1, 2018). "Death Wish decent, despite reloading with Bruce Willis". Toronto Star. Retrieved March 1, 2018.
Jump up ^ Lasalle, Mick (March 1, 2018). "'Death Wish' updated with more guns, cell phones and revenge". San Francisco Chronicle. Retrieved April 17, 2018.
External links[edit]
Official website
Death Wish on IMDb
Death Wish at Box Office Mojo
show
v
t
e
Brian Garfield's Death Wish
Novels
Death Wish
Death Sentence
Films
Death Wish (soundtrack)
Death Wish II (soundtrack)
Death Wish 3
Death Wish 4: The Crackdown
Death Wish V: The Face of Death
Death Wish (2018 film)
Other
Mohra
Death Sentence (2007 film)
show
v
t
e
Films by Eli Roth
Director
Cabin Fever (2002)
Hostel (2005)
Hostel: Part II (2007)
Grindhouse (segment "Thanksgiving", 2007)
The Green Inferno (2013)
Knock Knock (2015)
Death Wish (2018)
The House with a Clock in Its Walls (2018)
Producer only
2001 Maniacs (2005)
The Last Exorcism (2010)
The Man with the Iron Fists (2012)
Aftershock (2012)
The Last Exorcism Part II (2013)
Clown (2014)
Cabin Fever (2016)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Death_Wish_(2018_film)&oldid=849869056"
Categories:
2018 films
English-language films
Death Wish films
2010s action films
2010s crime drama films
2010s thriller drama films
American films
American action films
American action thriller films
American crime drama films
American film remakes
American thriller drama films
Films about murderers
Films based on American crime novels
Films scored by Ludwig Göransson
Films set in Chicago
Films shot in Chicago
Films shot in Montreal
Medical-themed films
Annapurna Pictures films
Metro-Goldwyn-Mayer films
Vertigo Films films
Films directed by Eli Roth
Hidden categories:
Use mdy dates from February 2018
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
العربية
Deutsch
Euskara
فارسی
Français
Հայերեն
Italiano
Magyar
Nederlands
日本語
Polski
Русский
Українська
中文
5 more
Edit links
This page was last edited on 11 July 2018, at 23:11 (UTC).
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: mw-jump-link #mw-head

values: mw-jump-link #p-search

value: p

value: th

attrs: colspan class style

attrs: scope style

values:
/wiki/MGM_Studios
mw-redirect
MGM Studios

values:
/wiki/Grim_Reaper
mw-redirect
Grim Reaper

values:
/wiki/Benicio_Del_Toro
mw-redirect
Benicio Del Toro

values: float: right; clear: right; margin: 0.5em 0 0.8em 1.4em; width:40%; padding: 10px; border: 1px solid #aaa; font-size: 88%; background-color: #F9F9F9;

values:
/wiki/Average_rating
mw-redirect
Average rating

values:
/wiki/Guardian_News_and_Media
mw-redirect
Guardian News and Media

values:
/wiki/Penske_Business_Media
mw-redirect
Penske Business Media

values:
/wiki/Associated_Newspapers
mw-redirect
Associated Newspapers

values:
/wiki/Fandango_Media
mw-redirect
Fandango Media

values:
/wiki/Chicago_Sun_Times
mw-redirect
Chicago Sun Times

values:
nofollow
http://deathwish.movie/
external text

values:
nofollow
https://www.imdb.com/title/tt1137450/
external text

values: nowraplinks collapsible autocollapse navbox-inner mw-collapsible mw-made-collapsible mw-collapsed

values: The House with a Clock in Its Walls (film)

values: Category:Films based on American crime novels

values: Category:Films scored by Ludwig Göransson

values: Category:Use mdy dates from February 2018

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Death_Wish_(2018_film)
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: ديث وش (فيلم) – Arabic

values:
interlanguage-link interwiki-eu
display: none;

values: آرزوی مرگ – Persian

values: Մահվան ծարավ – Armenian

values:
interlanguage-link interwiki-hy
display: none;

values: Il giustiziere della notte - Death Wish – Italian

values:
interlanguage-link interwiki-hu
display: none;

values: デス・ウィッシュ – Japanese

values:
interlanguage-link interwiki-pl
display: none;

values: Жажда смерти (фильм, 2018) – Russian

values: Жага смерті (фільм, 2018) – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values: All languages (initial selection from common choices by you and others)

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Death_Wish_2018_film rootpage-Death_Wish_2018_film skin-vector action-view


text:
Binary search algorithm
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about searching a finite sorted array. For searching continuous function values, see bisection method.
Binary search algorithm
Visualization of the binary search algorithm where 7 is the target value.
Class
Search algorithm
Data structure
Array
Worst-case performance
O(log n)
Best-case performance
O(1)
Average performance
O(log n)
Worst-case space complexity
O(1)
In computer science, binary search, also known as half-interval search,[1] logarithmic search,[2] or binary chop,[3] is a search algorithm that finds the position of a target value within a sorted array.[4][5] Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array.[6] Although specialized data structures designed for fast searching—such as hash tables—can be searched more efficiently, binary search applies to a wider range of problems.
Although the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.
There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays, efficiently solving a series of search problems in computational geometry and numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.
Contents
[hide]
1 Algorithm
1.1 Procedure
1.2 Approximate matches
2 Performance
3 Binary search versus other schemes
3.1 Hashing
3.2 Trees
3.3 Linear search
3.4 Set membership algorithms
3.5 Other data structures
4 Variations
4.1 Uniform binary search
4.2 Exponential search
4.3 Interpolation search
4.4 Fractional cascading
4.5 Fibonacci search
4.6 Noisy binary search
4.7 Quantum binary search
5 History
6 Implementation issues
7 Library support
8 See also
9 Notes and references
9.1 Notes
9.2 Citations
9.3 Works
10 External links
Algorithm[edit]
Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.[7]
Procedure[edit]
Given an array A of n elements with values or records A0, A1, ..., An−1, sorted such that A0 ≤ A1 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[7]
Set L to 0 and R to n − 1.
If L > R, the search terminates as unsuccessful.
Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
If Am < T, set L to m + 1 and go to step 2.
If Am > T, set R to m − 1 and go to step 2.
Now Am = T, the search is done; return m.
This iterative procedure keeps track of the search boundaries with the two variables. Some implementations may check whether the middle element is equal to the target at the end of the procedure. This results in a faster comparison loop, but requires one more iteration on average.[8]
Approximate matches[edit]
The above procedure only performs exact matches, finding the position of a target value. However, due to the ordered nature of sorted arrays, it is trivial to extend binary search to perform approximate matches. 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.[9]
Rank queries can be performed using a modified version of binary search. By returning m on a successful search, and L on an unsuccessful search, the number of elements less than the target value is returned instead.[9]
Predecessor and successor queries can be performed with rank queries. Once the rank of the target value is known, its predecessor is the element at the position given by its rank (as it is the largest element that is smaller than the target value). Its successor is the element after it (if it is present in the array) or at the next position after the predecessor (otherwise).[10] The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
Range queries are also straightforward. 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 keys matching those endpoints.[11]
Performance[edit]
A tree representing binary search. The array being searched here is [20, 30, 40, 50, 90, 100], and the target value is 40.
The performance of binary search can be analyzed by reducing the procedure to a binary comparison tree, where the root node is the middle element of the array; the middle element of the lower half is left of the root and the middle element of the upper half is right of the root. The rest of the tree is built in a similar fashion. This model represents binary search; 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, representing the successive elimination of elements.[6][12]
The worst case is ⌊ log 2  n + 1 ⌋ {\textstyle \lfloor \log _{2}n+1\rfloor } iterations of the comparison loop, where the ⌊ ⌋ {\textstyle \lfloor \rfloor } notation denotes the floor function that rounds its argument to the next-smallest integer and log 2 {\textstyle \log _{2}} is the binary logarithm. The worst case is reached when the search reaches the deepest level of the tree, equivalent to a binary search that has reduced to one element and, in each iteration, always eliminates the smaller subarray out of the two if they are not of equal size.[a][12]
On average, assuming that each element is equally likely to be searched, the procedure will most likely find the target value the second-deepest level of the tree. This is equivalent to a binary search that completes one iteration before the worst case, reached after log 2  n − 1 {\textstyle \log _{2}n-1} iterations. However, the tree may be unbalanced, with the deepest level partially filled, and equivalently, the array may not be divided perfectly by the search in some iterations, half of the time resulting in the smaller subarray being eliminated. The actual number of average iterations is slightly higher, at log 2  n − n − log 2  n − 1 n {\textstyle \log _{2}n-{\frac {n-\log _{2}n-1}{n}}} iterations.[6] In the best case, where target value is the middle element of the array, its position is returned after one iteration.[13] In terms of iterations, no search algorithm that works only by comparing elements can exhibit better average and worst-case performance than binary search.[12]
Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Again assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search, eliminating on average half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers, while guaranteeing that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only ⌊ log 2  n + 1 ⌋ {\textstyle \lfloor \log _{2}n+1\rfloor } times in the worst case, for all but enormous n {\textstyle n} , the slight increase in comparison loop efficiency does not compensate for the extra iteration. Knuth 1998 gives a value of 2 66 {\textstyle 2^{66}} (more than 73 quintillion)[14] elements for this variation to be faster.[b][15][16]
Fractional cascading can be used to speed up searches of the same value in multiple arrays. Where k {\textstyle k} is the number of arrays, searching each array for the target value takes O ( k log  n ) {\textstyle O(k\log n)} time; fractional cascading reduces this to O ( k + log  n ) {\textstyle O(k+\log n)} .[17]
Binary search versus other schemes[edit]
Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking O ( n ) {\textstyle O(n)} time for each such operation, and complicating memory use.[18] Other data structures support much more efficient insertion and deletion, and also fast exact matching. However, binary search applies to a wide range of search problems, usually solving them in O ( log  n ) {\textstyle O(\log n)} time regardless of the type or structure of the values themselves.
Hashing[edit]
For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records;[19] most implementations require only amortized constant time on average.[c][21] However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record.[22] Binary search is ideal for such matches, performing them in logarithmic time. In addition, all operations possible on a sorted array can be performed—such as finding the smallest and largest key and performing range searches.[23]
Trees[edit]
Binary search trees are searched using an algorithm similar to binary search.
A binary search tree is a binary tree data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.[24]
However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This applies even to balanced binary search trees, binary search trees that balance their own nodes—as they rarely produce optimally-balanced trees—but to a lesser extent. Although unlikely, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching n {\textstyle n} comparisons.[d] Binary search trees take more space than sorted arrays.[26]
Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can effectively be structured in filesystems. The B-tree generalizes this method of tree organization; B-trees are frequently used to organize long-term storage such as databases and filesystems.[27][28]
Linear search[edit]
Linear search is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short.[e][30] If the array must first be sorted, that cost must be amortized over any searches. Sorting the array also enables efficient approximate matches and other operations.[31]
Set membership algorithms[edit]
A related problem to search is set membership. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A bit array is the simplest, useful when the range of keys is limited; it is very fast, requiring only O ( 1 ) {\textstyle O(1)} time.[32] The Judy1 type of Judy array handles 64-bit keys efficiently.
For approximate results, Bloom filters, another probabilistic data structure based on hashing, store a set of keys by encoding the keys using a bit array and multiple hash functions. Bloom filters are much more space-efficient than bitarrays in most cases and not much slower: with k {\textstyle k} hash functions, membership queries require only O ( k ) {\textstyle O(k)} time. However, Bloom filters suffer from false positives.[f][g][34]
Other data structures[edit]
There exist data structures that may improve on binary search in some cases for both searching and other operations available for sorted arrays. For example, searches, approximate matches, and the operations available to sorted arrays can be performed more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays. However, while these operations can always be done at least efficiently on a sorted array regardless of the keys, such data structures are usually only faster because they exploit the properties of keys with a certain attribute (usually keys that are small integers), and thus will be time or space consuming for keys that lack that attribute.[23] Some structures, such as Judy arrays, use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching.[35]
Variations[edit]
Uniform binary search[edit]
Uniform binary search stores the difference between the current and the two next possible middle elements instead of specific bounds.
Main article: Uniform binary search
Uniform binary search stores, instead of the lower and upper bounds, the index of the middle element and the change in the middle element from the current iteration to the next iteration. Each step reduces the change by about half. For example, if the array to be searched was [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], the middle element would be 6. Uniform binary search works on the basis that the difference between the index of middle element of the array and the left and right subarrays is the same. 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.[36] To reduce the search space, the algorithm either adds or subtracts this change from the middle element. The main advantage of uniform binary search is that the procedure can store a table of the differences between indices for each iteration of the procedure, which may improve the algorithm's performance on some systems.[37]
Exponential search[edit]
Visualization of exponential searching finding the upper bound for the subsequent binary search. In this case, the exponential search is operating on a bounded array.
Main article: Exponential 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 of the exponential search 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.[38]
Interpolation search[edit]
Visualization of interpolation search. 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.
Main article: Interpolation search
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. This is only possible if the array elements are numbers. 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.[39] When the distribution of the array elements is uniform or near uniform, it makes O ( log  log  n ) {\textstyle O(\log \log n)} comparisons.[39][40][41]
In practice, interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation. Although its time complexity grows more slowly than binary search, this only compensates for the extra computation for large arrays.[39]
Fractional cascading[edit]
Main article: Fractional cascading
Fractional cascading is a technique that speeds up binary searches for the same element for both exact and approximate matching in "catalogs" (arrays of sorted elements) associated with vertices in graphs. Searching each catalog separately requires O ( k log  n ) {\textstyle O(k\log n)} time, where k {\textstyle k} is the number of catalogs. Fractional cascading reduces this to O ( k + log  n ) {\textstyle O(k+\log n)} by storing specific information in each catalog about other catalogs.[17]
Fractional cascading was originally developed to efficiently solve various computational geometry problems, but it also has been applied elsewhere, in domains such as data mining and Internet Protocol routing.[17]
Fibonacci search[edit]
Fibonacci search on the function f ( x ) = sin  ( ( x + 1 10 ) π ) {\textstyle f(x)=\sin {}((x+{\frac {1}{10}})\pi )} on the unit interval [ 0 , 1 ] {\textstyle {[0,1]}} . The algorithm finds an interval containing the maximum of f {\textstyle f} with a length less than or equal to 1 10 {\textstyle {\frac {1}{10}}} in the above example. In three iterations, it returns the interval [ 5 13 , 6 13 ] {\textstyle {\left[{\frac {5}{13}},{\frac {6}{13}}\right]}} , which is of length 1 13 {\textstyle {\frac {1}{13}}} .
Main article: Fibonacci search technique
Fibonacci search is a method similar to binary search that successively shortens the interval in which the maximum of a unimodal function lies. Given a finite interval, a unimodal function, and the maximum length of the resulting interval, Fibonacci search finds a Fibonacci number such that if the interval is divided equally into that many subintervals, the subintervals would be shorter than the maximum length. After dividing the interval, it eliminates the subintervals in which the maximum cannot lie until one or more contiguous subintervals remain.[42][43]
Noisy binary search[edit]
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.[h][45][46] The noisy binary search problem can be considered as a case of the Rényi-Ulam game,[47] which Alfréd Rényi introduced in 1961.[48]
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 faster performance on quantum computers. Høyer, Neerbek & Shi 2002 proved that any exact quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least 1 π ( ln  n − 1 ) ≈ 0.220 log 2  n {\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.220\log _{2}n} queries in the worst case, where ln {\textstyle \ln } is the natural logarithm.[49] Childs, Landahl & Parrilo 2007 provided 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.[50]
History[edit]
In 1946, John Mauchly made the first mention of binary search as part of the Moore School Lectures, the first ever set of lectures regarding any computer-related topic.[51] 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.[53] 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 presented to Donald Knuth in 1971 by A. K. Chandra of Stanford University and published in Knuth's The Art of Computer Programming.[51] In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading as a method to solve numerous search problems in computational geometry.[17][54][55]
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,[56] and another study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.[57] 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.[58]
In a practical implementation, the variables used to represent the indices will often be of fixed size, and this can result in an arithmetic overflow for very large arrays. If the midpoint of the span is calculated as (L + R) / 2, then the value of L + R may exceed the range of integers of the data type used to store the midpoint, even if L and R are within the range. If L and R are nonnegative, this can be avoided by calculating the midpoint as L + (R − L) / 2.[59]
If the target value is greater than the greatest value in the array, and the last index of the array is the maximum representable value of L, the value of L will eventually become too large and overflow. A similar problem will occur if the target value is smaller than the least value in the array and the first index of the array is the smallest representable value of R. In particular, this means that R must not be an unsigned type if the array starts with index 0.
An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once L exceeds 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, in his assignment of binary search, most of the programmers who implemented binary search incorrectly made an error defining the exit conditions.[8][60]
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 so).[61]
C++'s Standard Template Library provides the functions binary_search(), lower_bound(), upper_bound() and equal_range().[62]
COBOL provides the SEARCH ALL verb for performing binary searches on COBOL ordered tables.[63]
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 Lists, respectively.[64][65]
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).[66]
Python provides the bisect module.[67]
Ruby's Array class includes a bsearch method with built-in approximate matching.[68]
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.[69]
For Objective-C, the Cocoa framework provides the NSArray -indexOfObject:inSortedRange:options:usingComparator: method in Mac OS X 10.6+.[70] Apple's Core Foundation C framework also contains a CFArrayBSearchValues() function.[71]
See also[edit]
Computer science portal
Bisection method – 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]
Notes[edit]
Jump up ^ This happens as binary search will not always divide the array perfectly. Take for example the array [1, 2 ... 16]. The first iteration will select the midpoint of 8. On the left subarray are eight elements, but on the right are nine. If the search takes the right path, there is a higher chance that the search will make the maximum number of comparisons.[12]
Jump up ^ Knuth showed on his MIX computer model, intended to represent an ordinary computer, that the average running time of this variation for a successful search is 17.5 log 2  n + 17 {\textstyle 17.5\log _{2}n+17} units of time compared to 18 log 2  n − 16 {\textstyle 18\log _{2}n-16} units for regular binary search. The time complexity for this variation grows slightly more slowly, but at the cost of higher initial complexity.[15]
Jump up ^ It is possible to perform hashing in guaranteed constant time.[20]
Jump up ^ The worst binary search tree for searching can be produced by inserting the values in sorted or near-sorted order or in an alternating lowest-highest record pattern.[25]
Jump up ^ Knuth 1998 performed a formal time performance analysis of both of these search algorithms. On Knuth's hypothetical MIX computer, intended to represent an ordinary computer, binary search takes on average 18 log  n − 16 {\textstyle 18\log n-16} units of time for a successful search, while linear search with a sentinel node at the end of the list takes 1.75 n + 8.5 − n mod 2 4 n {\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}} units. Linear search has lower initial complexity because it requires minimal computation, but it quickly outgrows binary search in complexity. On the MIX computer, binary search only outperforms linear search with a sentinel if n > 44 {\textstyle n>44} .[12][29]
Jump up ^ As simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.[33]
Jump up ^ There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits cuckoo hashing to gain these advantages.[33]
Jump up ^ Using noisy comparisons, Ben-Or & Hassidim 2008 established that any 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.[44]
Jump up ^ That is, arrays of length 1, 3, 7, 15, 31 ...[52]
Citations[edit]
Jump up ^ Willams, Jr., Louis F. (1975). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. pp. 95–101. doi:10.1145/503561.503582.
^ Jump up to: a b Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
Jump up ^ Butterfield & Ngondi 2016.
Jump up ^ Cormen et al. 2009, p. 39.
Jump up ^ Weisstein, Eric W. "Binary Search". MathWorld.
^ Jump up to: a b c Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752.
^ Jump up to: a b Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
^ Jump up to: a b c Bottenbruch, Hermann (1962). "Structure and Use of ALGOL 60". Journal of the ACM. 9 (2): 161–211. doi:10.1145/321119.321120. Procedure is described at p. 214 (§43), titled "Program for Binary Search".
^ Jump up to: a b Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".
Jump up ^ Goldman & Goldman 2008, pp. 461–463.
Jump up ^ Sedgewick & Wayne 2011, §3.1, subsection "Range queries".
^ Jump up to: a b c d e Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".
Jump up ^ Chang 2003, p. 169.
Jump up ^ Sloane, Neil. Table of n, 2n for n = 0..1000. Part of OEIS A000079. Retrieved 30 April 2016.
^ Jump up to: a b Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".
Jump up ^ Rolfe, Timothy J. (1997). "Analytic derivation of comparisons in binary search". ACM SIGNUM Newsletter. 32 (4): 15–19. doi:10.1145/289251.289255.
^ Jump up to: a b c d Chazelle, Bernard; Liu, Ding (2001). Lower bounds for intersection searching and fractional cascading in higher dimension (PDF). 33rd ACM Symposium on Theory of Computing. pp. 322–329. doi:10.1145/380752.380818.
Jump up ^ Knuth 1997, §2.2.2 ("Sequential Allocation").
Jump up ^ Knuth 1998, §6.4 ("Hashing").
Jump up ^ Knuth 1998, §6.4 ("Hashing"), subsection "History".
Jump up ^ Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (August 1994). "Dynamic Perfect Hashing: Upper and Lower Bounds". SIAM Journal on Computing. 23 (4): 738–761. doi:10.1137/S0097539791194094.
Jump up ^ Morin, Pat. "Hash Tables" (PDF). p. 1. Retrieved 28 March 2016.
^ Jump up to: a b Beame, Paul; Fich, Faith E. (2001). "Optimal Bounds for the Predecessor Problem and Related Problems". Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
Jump up ^ Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".
Jump up ^ Knuth 1998, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?".
Jump up ^ Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".
Jump up ^ Knuth 1998, §5.4.9 ("Disks and Drums").
Jump up ^ Knuth 1998, §6.2.4 ("Multiway trees").
Jump up ^ Knuth 1998, Answers to Exercises (§6.2.1) for "Exercise 5".
Jump up ^ Knuth 1998, §6.2.1 ("Searching an ordered table").
Jump up ^ Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").
Jump up ^ Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").
^ Jump up to: a b Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo Filter: Practically Better Than Bloom. Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. pp. 75–88. doi:10.1145/2674005.2674994.
Jump up ^ Bloom, Burton H. (1970). "Space/time Trade-offs in Hash Coding with Allowable Errors" (PDF). Communications of the ACM. 13 (7): 422–426. doi:10.1145/362686.362692.
Jump up ^ Silverstein, Alan, Judy IV Shop Manual (PDF), Hewlett-Packard, pp. 80–81
Jump up ^ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "An important variation".
Jump up ^ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".
Jump up ^ Moffat & Turpin 2002, p. 33.
^ Jump up to: a b c Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Interpolation search".
Jump up ^ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 22".
Jump up ^ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Interpolation search—a log log n search". Communications of the ACM. 21 (7): 550–553. doi:10.1145/359545.359557.
Jump up ^ Kiefer, J. (1953). "Sequential Minimax Search for a Maximum". Proceedings of the American Mathematical Society. 4 (3): 502–506. JSTOR 2032161. doi:10.2307/2032161.
Jump up ^ Hassin, Refael (1981). "On Maximizing Functions by Fibonacci Search". Fibonacci Quarterly. 19: 347–351.
Jump up ^ Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)" (PDF). 49th Symposium on Foundations of Computer Science: 221–230. doi:10.1109/FOCS.2008.58.
Jump up ^ Pelc, Andrzej (1989). "Searching with known error probability". Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.
Jump up ^ Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.
Jump up ^ Pelc, Andrzej (2002). "Searching games with errors—fifty years of coping with liars". Theoretical Computer Science. 270 (1-2): 71–109. doi:10.1016/S0304-3975(01)00303-6.
Jump up ^ Rényi, Alfréd (1961). "On a problem in information theory". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (in Hungarian). 6: 505–516. MR 0143666.
Jump up ^ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness". Algorithmica. 34 (4): 429–448. doi:10.1007/s00453-002-0976-3.
Jump up ^ Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Quantum algorithms for the ordered search problem via semidefinite programming". Physical Review A. 75 (3). doi:10.1103/PhysRevA.75.032335.
^ Jump up to: a b Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
Jump up ^ "2n−1". OEIS A000225. Retrieved 7 May 2016.
Jump up ^ Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer (PDF). Proceedings of Symposia in Applied Mathematics. 10. pp. 180–181. doi:10.1090/psapm/010.
Jump up ^ Chazelle, Bernard; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF). Algorithmica. 1 (1): 133–162. doi:10.1007/BF01840440.
Jump up ^ Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica, 1 (1): 163–191, doi:10.1007/BF01840441
Jump up ^ Bentley 2000, §4.1 ("The Challenge of Binary Search").
Jump up ^ Pattis, Richard E. (1988). "Textbook errors in binary searching". SIGCSE Bulletin. 20: 190–194. doi:10.1145/52965.53012.
Jump up ^ Bloch, Joshua (2 June 2006). "Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken". Google Research Blog. Retrieved 21 April 2016.
Jump up ^ Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (PDF). Information Processing Letters. 87 (2): 67–71. doi:10.1016/S0020-0190(03)00263-1.
Jump up ^ Bentley 2000, §4.4 ("Principles").
Jump up ^ "bsearch – binary search a sorted table". The Open Group Base Specifications (7th ed.). The Open Group. 2013. Retrieved 28 March 2016.
Jump up ^ Stroustrup 2013, §32.6.1 ("Binary Search").
Jump up ^ Unisys (2012), COBOL ANSI-85 Programming Reference Manual, 1, pp. 598–601
Jump up ^ "java.util.Arrays". Java Platform Standard Edition 8 Documentation. Oracle Corporation. Retrieved 1 May 2016.
Jump up ^ "java.util.Collections". Java Platform Standard Edition 8 Documentation. Oracle Corporation. Retrieved 1 May 2016.
Jump up ^ "List<T>.BinarySearch Method (T)". Microsoft Developer Network. Retrieved 10 April 2016.
Jump up ^ "8.5. bisect — Array bisection algorithm". The Python Standard Library. Python Software Foundation. Retrieved 10 April 2016.
Jump up ^ Fitzgerald 2007, p. 152.
Jump up ^ "Package sort". The Go Programming Language. Retrieved 28 April 2016.
Jump up ^ "NSArray". Mac Developer Library. Apple Inc. Retrieved 1 May 2016.
Jump up ^ "CFArray". Mac Developer Library. Apple Inc. Retrieved 1 May 2016.
Works[edit]
Alexandrescu, Andrei (2010). The D Programming Language. Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 0-321-63536-1.
Bentley, Jon (2000) [1986]. Programming Pearls (2nd ed.). Addison-Wesley. ISBN 0-201-65788-0.
Butterfield, Andrew; Ngondi, Gerard E. (2016). A Dictionary of Computer Science (7th ed.). Oxford, UK: Oxford University Press. ISBN 978-0199688975.
Chang, Shi-Kuo (2003). Data Structures and Algorithms. Software Engineering and Knowledge Engineering. 13. Singapore: World Scientific. ISBN 978-981-238-348-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
Fitzgerald, Michael (2007). Ruby Pocket Reference. Sebastopol, CA: O'Reilly Media. ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A Practical Guide to Data Structures and Algorithms using Java. Boca Raton: CRC Press. ISBN 978-1-58488-455-2.
Knuth, Donald (1997). Fundamental Algorithms. The Art of Computer Programming. 1 (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 0-201-89683-4
Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 0-201-89685-0
Knuth, Donald (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. 4A (1st ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 0-201-03804-8
Leiss, Ernst (2007). A Programmer's Companion to Algorithm Analysis. Boca Raton, FL: CRC Press. ISBN 1-58488-673-0.
Moffat, Alistair; Turpin, Andrew (2002). Compression and Coding Algorithms. Hamburg, Germany: Kluwer Academic Publishers. ISBN 978-0-7923-7668-2. doi:10.1007/978-1-4615-0935-6.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-57351-3. Condensed web version: ; book version .
Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2.
External links[edit]
The Wikibook Algorithm implementation has a page on the topic of: Binary search
NIST Dictionary of Algorithms and Data Structures: binary search
Retrieved from "https://en.wikipedia.org/w/index.php?title=Binary_search_algorithm&oldid=807168498"
Categories:
Search algorithms
Hidden categories:
CS1 Hungarian-language sources (hu)
Good articles
Use dmy dates from April 2016
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Wikibooks
Languages
العربية
Azərbaycanca
Български
Čeština
Deutsch
Ελληνικά
Español
فارسی
Français
한국어
हिन्दी
Bahasa Indonesia
Interlingua
Italiano
עברית
Македонски
日本語
Norsk
Polski
Português
Română
Русский
Slovenčina
Slovenščina
Српски / srpski
Suomi
Svenska
ไทย
Türkçe
Українська
Tiếng Việt
粵語
中文
Edit links
This page was last edited on 26 October 2017, at 10:03.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

key: html

type: local

value: div

attrs: id class

values: mw-page-base noprint

values: mw-head-base noprint

value: a

value: img

attrs: alt src width height srcset data-file-width data-file-height

values: This is a good article. Click here for more information.

attrs: href title

attrs: class id

attrs: id class lang

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

attrs: role class

values:
note
hatnote navigation-not-searchable

value: caption

attrs: href class

value: td

attrs: colspan style

value: tr

values:
/wiki/Data_structures
mw-redirect
Data structures

values:
/wiki/Hash_tables
mw-redirect
Hash tables

attrs: alt src width height class srcset data-file-width data-file-height

values: vertical-align: -0.838ex; width:11.966ex; height:2.843ex;

values: {\textstyle \lfloor \log _{2}n+1\rfloor }

values: vertical-align: -0.838ex; width:2.086ex; height:2.843ex;

values:
/wiki/Floor_function
mw-redirect
Floor function

values: vertical-align: -0.838ex; width:4.065ex; height:2.676ex;

values: vertical-align: -0.838ex; width:9.881ex; height:2.676ex;

values: vertical-align: -1.171ex; width:18.281ex; height:4.009ex;

values: vertical-align: -0.338ex; width:1.405ex; height:1.676ex;

values: vertical-align: -0.338ex; width:3.064ex; height:2.676ex;

values: vertical-align: -0.338ex; width:1.222ex; height:2.176ex;

values: vertical-align: -0.838ex; width:10.018ex; height:2.843ex;

values: vertical-align: -0.838ex; width:12.482ex; height:2.843ex;

values: Edit section: Binary search versus other schemes

values: vertical-align: -0.838ex; width:5.019ex; height:2.843ex;

values: vertical-align: -0.838ex; width:8.409ex; height:2.843ex;

values:
/wiki/Associative_arrays
mw-redirect
Associative arrays

values:
/wiki/Balanced_binary_search_tree
mw-redirect
Balanced binary search tree

values: vertical-align: -0.838ex; width:4.787ex; height:2.843ex;

values: vertical-align: -0.838ex; width:4.836ex; height:2.843ex;

values: vertical-align: -0.838ex; width:11.901ex; height:2.843ex;

values: {\textstyle \lfloor \log _{2}x+1\rfloor }

values: vertical-align: -0.838ex; width:7.878ex; height:2.843ex;

values: vertical-align: -0.338ex; width:1.34ex; height:1.676ex;

values: vertical-align: -0.838ex; width:11.8ex; height:2.843ex;

values: vertical-align: -1.338ex; width:22.531ex; height:3.676ex;

values: vertical-align: -0.838ex; width:4.705ex; height:2.843ex;

values: vertical-align: -0.671ex; width:1.289ex; height:2.509ex;

values: vertical-align: -1.338ex; width:2.495ex; height:3.676ex;

values: vertical-align: -1.838ex; width:8.25ex; height:4.843ex;

values: vertical-align: -0.838ex; width:5.857ex; height:2.676ex;

values: vertical-align: -1.171ex; width:26.094ex; height:3.509ex;

values: vertical-align: -0.338ex; width:1.96ex; height:2.176ex;

values: vertical-align: -0.838ex; width:23.778ex; height:2.676ex;

values: {\textstyle 4\log _{605}n\approx 0.433\log _{2}n}

values: display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle

values: margin:0.5em 0 0.5em 1em;border:solid #aaa 1px

values: vertical-align: -0.838ex; width:15.617ex; height:2.676ex;

values: vertical-align: -0.838ex; width:13.787ex; height:2.676ex;

values: vertical-align: -0.838ex; width:12.725ex; height:2.676ex;

values: vertical-align: -1.338ex; width:21.233ex; height:3.843ex;

values: vertical-align: -0.338ex; width:6.86ex; height:2.176ex;

values: vertical-align: -2.671ex; width:22.531ex; height:6.343ex;

values: vertical-align: -0.838ex; width:38.581ex; height:2.843ex;

values: vertical-align: -0.338ex; width:1.212ex; height:1.676ex;

values:
reflist mw-references-wrap
list-style-type: lower-alpha;

values:
nofollow
external text
//doi.org/10.1145%2F503561.503582

values:
nofollow
external text
//doi.org/10.1145%2F362663.362752

values:
nofollow
external text
//doi.org/10.1145%2F321119.321120

values:
nofollow
external text
https://oeis.org/A000079/b000079.txt

values: On-Line Encyclopedia of Integer Sequences

values:
nofollow
external text
https://oeis.org/A000079

values:
nofollow
external text
//doi.org/10.1145%2F289251.289255

values:
nofollow
external text
//doi.org/10.1145%2F380752.380818

values:
nofollow
external text
//doi.org/10.1006%2Fjcss.2002.1822

values:
nofollow
external text
//doi.org/10.1145%2F362686.362692

values:
nofollow
external text
//doi.org/10.1145%2F359545.359557

values: Proceedings of the American Mathematical Society

values:
nofollow
external text
//www.jstor.org/stable/2032161

values:
nofollow
external text
//doi.org/10.2307%2F2032161

values: Annual IEEE Symposium on Foundations of Computer Science

values:
nofollow
external text
//doi.org/10.1109%2FFOCS.2008.58

values:
/wiki/Ronald_Rivest
mw-redirect
Ronald Rivest

values:
nofollow
external text
//doi.org/10.1145%2F800133.804351

values:
nofollow
external text
http://arxiv.org/pdf/quant-ph/0608161

values:
nofollow
external text
//doi.org/10.1103%2FPhysRevA.75.032335

values:
nofollow
external text
http://oeis.org/A000225

values:
nofollow
external text
http://arxiv.org/pdf/0811.4510v2.pdf

values:
nofollow
external text
//doi.org/10.1090%2Fpsapm%2F010

values:
nofollow
external text
//doi.org/10.1007%2FBF01840440

values:
nofollow
external text
//doi.org/10.1007%2FBF01840441

values:
nofollow
external text
//doi.org/10.1145%2F52965.53012

values:
nofollow
http://golang.org/pkg/sort/
external text

values: -moz-column-width: 30em; -webkit-column-width: 30em; column-width: 30em; list-style-type: decimal;

values:
nofollow
http://algs4.cs.princeton.edu/home/
external text

values: closed access publication – behind paywall

values: div-col columns column-count column-count-2

values: -moz-column-count: 2; -webkit-column-count: 2; column-count: 2; font-size:90%;

values: Category:CS1 Hungarian-language sources (hu)

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Binary_search_algorithm
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: portal navigation p-wikibase-otherprojects p-wikibase-otherprojects-label

values:
uls-settings-trigger
Language settings
0
button
true

values: خوارزمية بحث ثنائي – Arabic

values: Двоично търсене – Bulgarian

values: Δυαδική αναζήτηση – Greek

values: الگوریتم جستجوی دودویی – Persian

values: 이진 검색 알고리즘 – Korean

values: द्विआधारी खोज प्रणाली – Hindi

values: חיפוש בינארי – Hebrew

values: Бинарно пребарување – Macedonian

values: Двоичный поиск – Russian

values: Бинарна претрага – Serbian

values: การค้นหาแบบทวิภาค – Thai

values: Двійковий пошук – Ukrainian

values: 二分搜索算法 – Chinese

values: /static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x

values: /static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Binary_search_algorithm rootpage-Binary_search_algorithm vector-experimental-print-styles vector-nav-directionality skin-vector action-view


text:
Larry Nance Jr.
From Wikipedia, the free encyclopedia
This is the latest accepted revision, reviewed on 25 May 2018.
Jump to: navigation, search
Larry Nance Jr.
Nance Jr. with Cleveland in 2018
No. 22 – Cleveland Cavaliers
Position
Power forward / Center
League
NBA
Personal information
Born
(1993-01-01) January 1, 1993 (age 25)
Akron, Ohio
Nationality
American
Listed height
6 ft 9 in (2.06 m)
Listed weight
230 lb (104 kg)
Career information
High school
Revere (Richfield, Ohio)
College
Wyoming (2011–2015)
NBA draft
2015 / Round: 1 / Pick: 27th overall
Selected by the Los Angeles Lakers
Playing career
2015–present
Career history
2015–2018
Los Angeles Lakers
2018–present
Cleveland Cavaliers
Career highlights and awards
2× First-team All-MWC (2014, 2015)
MWC Defensive Player of the Year (2015)
2× MWC All-Defensive Team (2014, 2015)
Stats at NBA.com
Stats at Basketball-Reference.com
Larry Donnell Nance Jr. (born January 1, 1993) is an American professional basketball player for the Cleveland Cavaliers of the National Basketball Association (NBA). He played college basketball for Wyoming, where he was considered one of the best big men in the Mountain West Conference[1] after leading the 2014–15 Wyoming Cowboys to their first NCAA Tournament appearance since 2002. Nance was drafted 27th overall in the 2015 NBA draft by the Los Angeles Lakers. In February 2018, he was traded to the Cleveland Cavaliers.
Contents
[hide]
1 High school and college career
1.1 College statistics
2 Professional career
2.1 Los Angeles Lakers (2015–2018)
2.2 Cleveland Cavaliers (2018–present)
3 NBA career statistics
3.1 Regular season
4 Personal life
5 References
6 External links
High school and college career[edit]
Nance going up for a dunk in 2014
Nance attended Revere High School near Akron, Ohio, growing into a then-6'7" body by his senior year after playing point guard for the freshman team standing at 5'11". He averaged 18.2 points, 9.5 rebounds and 3.0 blocks per game as a senior for the Minutemen.[2]
In his four-year college career at Wyoming, Nance averaged 11.3 points, 6.6 rebounds, 1.4 assists, 1.1 steals, and 1.1 blocks in 123 games.[3]
College statistics[edit]
Year
Team
GP
GS
MPG
FG%
3P%
FT%
RPG
APG
SPG
BPG
PPG
2011–12 Wyoming 33 0 17.9 .462 .333 .814 4.0 .4 .8 .6 4.1
2012–13 Wyoming 33 33 32.0 .533 .345 .750 6.9 1.2 1.3 .7 10.7
2013–14 Wyoming 26 26 34.7 .544 .243 .758 8.6 1.6 1.4 2.1 15.4
2014–15 Wyoming 31 31 34.9 .514 .333 .786 7.2 2.5 1.2 1.2 16.1
Career 123 90 29.5 .521 .308 .771 6.6 1.4 1.1 1.1 11.3
Professional career[edit]
Los Angeles Lakers (2015–2018)[edit]
On June 25, 2015, Nance was selected with the 27th overall pick in the 2015 NBA draft by the Los Angeles Lakers.[4] On July 10, he signed his rookie scale contract with the Lakers.[5] He made his NBA debut on November 6 against the Brooklyn Nets, recording six points and five rebounds in a 104–98 win.[6] On December 7, he made his first start for the Lakers after replacing Julius Randle at the starting power forward spot against the Toronto Raptors.[7] On December 27, he recorded his first career double-double with 17 points and 11 rebounds in a 112–96 loss to the Memphis Grizzlies.[8]
On November 20, 2016, Nance scored a career-high 18 points in a 118–110 loss to the Chicago Bulls.[9] On December 25, 2016, he was ruled out for four weeks after suffering an injury to his left knee.[10]
On November 3, 2017, Nance was ruled out for four to six weeks after fracturing the second metacarpal on his left hand the previous night against the Portland Trail Blazers.[11] He missed 11 games as a result.[12]
Cleveland Cavaliers (2018–present)[edit]
On February 8, 2018, Nance was traded, along with Jordan Clarkson, to the Cleveland Cavaliers in exchange for Isaiah Thomas, Channing Frye and a 2018 first-round draft pick.[13] After playing his first two games as a Cavalier with No. 24, he switched to No. 22 permanently on February 22 after the NBA allowed him to wear his father's retired No. 22 jersey.[14] On March 5, 2018, he posted career highs with 22 points and 15 rebounds in his first start for Cleveland, as the Cavaliers defeated the Detroit Pistons 112–90.[15] On March 13, 2018, in a 129–107 win over the Phoenix Suns, Nance had only four points, ending his career-best string of seven consecutive double-digit scoring games.[16]
NBA career statistics[edit]
Legend
GP Games played GS Games started MPG Minutes per game
FG% Field goal percentage 3P% 3-point field goal percentage FT% Free throw percentage
RPG Rebounds per game APG Assists per game SPG Steals per game
BPG Blocks per game PPG Points per game Bold Career high
Regular season[edit]
Year
Team
GP
GS
MPG
FG%
3P%
FT%
RPG
APG
SPG
BPG
PPG
2015–16 L.A. Lakers 63 22 20.1 .527 .100 .681 5.0 .7 .9 .4 5.5
2016–17 L.A. Lakers 63 7 22.9 .526 .278 .738 5.9 1.5 1.3 .6 7.1
2017–18 L.A. Lakers 42 17 22.0 .601 .250 .632 6.8 1.4 1.4 .5 8.6
2017–18 Cleveland 24 10 20.8 .550 .125 .720 7.0 1.0 1.2 .8 8.9
Career 192 56 21.5 .547 .224 .689 5.9 1.2 1.2 .5 7.1
Personal life[edit]
Nance is the son of Larry Nance, a former professional basketball player for the Cleveland Cavaliers and Phoenix Suns.[1] Nance Sr. was a three-time NBA All-Star and won the league's first Slam Dunk Contest. Nance Jr. was a participant in the 2018 Slam Dunk Contest, coming in second. One of the younger Nance's dunks was a tribute to his father, as he wore a retro 1984 Phoenix Suns uniform and performed a cradle dunk as his father had done that year to win the inaugural dunk contest. Larry Sr. and Jr. later teamed up for an alley-oop dunk, with the elder Nance throwing the ball up to his son, who slammed it through the hoop.[17]
Nance Jr. has been diagnosed with Crohn's disease.[18]
References[edit]
^ Jump up to: a b "Larry Nance Jr. Bio". GoWyo.com. Archived from the original on 16 March 2015. Retrieved 17 March 2015.
Jump up ^ Pluto, Terry. "Larry Nance Jr. happy to continue his long, winding basketball road to Wyoming: Terry Pluto" (9 May 2011). Plain Dealer Publishing Co. The Plain Dealer. Retrieved 26 June 2015.
Jump up ^ "Larry Nance Stats". Sports-Reference.com. Retrieved June 26, 2015.
Jump up ^ "Lakers Select Larry Nance in First Round". NBA.com. June 25, 2015. Retrieved June 27, 2015.
Jump up ^ "Lakers Sign Larry Nance, Jr". NBA.com. July 10, 2015. Retrieved July 13, 2015.
Jump up ^ "Bryant, Lakers beat winless Nets for 1st victory". NBA.com. November 6, 2015. Retrieved November 10, 2015.
Jump up ^ "Larry Nance Jr. 2015-16 Game Log". Basketball-Reference.com. Retrieved December 27, 2015.
Jump up ^ "Conley, Green lead Grizzlies past Lakers, 112-96". NBA.com. December 27, 2015. Retrieved December 27, 2015.
Jump up ^ "Jimmy Butler's 40 points boost Bulls past Lakers, 118-110". ESPN.com. November 20, 2016. Retrieved November 20, 2016.
Jump up ^ "Larry Nance Jr. Injury Update". NBA.com. December 25, 2016. Retrieved December 26, 2016.
Jump up ^ "Larry Nance Jr. Medical Update". NBA.com. November 3, 2017. Retrieved November 3, 2017.
Jump up ^ "Clippers hang on to beat Lakers 120-115 for 3rd win in row". ESPN.com. November 27, 2017. Retrieved November 28, 2017.
Jump up ^ "Cavaliers Acquire Jordan Clarkson and Larry Nance Jr. From Lakers". NBA.com. February 8, 2018. Retrieved February 8, 2018.
Jump up ^ "Wizards hold off LeBron, new-look Cavaliers 110-103". ESPN.com. February 22, 2018. Retrieved February 22, 2018.
Jump up ^ "LeBron, Nance power Cavaliers past Pistons 112-90". ESPN.com. March 5, 2018. Retrieved March 5, 2018.
Jump up ^ "James' triple-double leads Cavaliers past lowly Suns". ESPN.com. March 13, 2018. Retrieved March 13, 2018.
Jump up ^ Larry Nance Jr. found the best way to honor his 1984 Slam Dunk Champ dad - USA Today
Jump up ^ Darby, Luke (October 26, 2017). "The Real-Life Diet of Larry Nance Jr., the NBA Player with Crohn's Disease". gq.com. Retrieved February 8, 2018.
External links[edit]
National Basketball Association portal
Wikimedia Commons has media related to Larry Nance Jr..
Career statistics and player information from NBA.com, or Basketball-Reference.com
Larry Nance Jr. at gowyo.com
Larry Nance Jr. at draftexpress.com
[show]
v
t
e
Cleveland Cavaliers current roster
0 Love
1 Hood
3 Hill
5 Smith
8 Clarkson
9 White
10 Holland (TW)
13 Thompson
15 Perrantes (TW)
16 Osman
21 Perkins
22 Nance
23 James
26 Korver
32 Green
41 Žižić
81 Calderón
Head coach: Lue
Assistant coaches:
Boylan
Drew (Assoc. HC)
Handy
Jones
Longabardi
Posey
Potapenko
[show]
v
t
e
2015 NBA draft
First round
Karl-Anthony Towns
D'Angelo Russell
Jahlil Okafor
Kristaps Porziņģis
Mario Hezonja
Willie Cauley-Stein
Emmanuel Mudiay
Stanley Johnson
Frank Kaminsky
Justise Winslow
Myles Turner
Trey Lyles
Devin Booker
Cameron Payne
Kelly Oubre Jr.
Terry Rozier
Rashad Vaughn
Sam Dekker
Jerian Grant
Delon Wright
Justin Anderson
Bobby Portis
Rondae Hollis-Jefferson
Tyus Jones
Jarell Martin
Nikola Milutinov
Larry Nance Jr.
R. J. Hunter
Chris McCullough
Kevon Looney
Second round
Cedi Osman
Montrezl Harrell
Jordan Mickey
Anthony Brown
Willy Hernangómez
Rakeem Christmas
Richaun Holmes
Darrun Hilliard
Juan Pablo Vaulet
Josh Richardson
Pat Connaughton
Olivier Hanlan
Joe Young
Andrew Harrison
Marcus Thornton
Norman Powell
Artūras Gudaitis
Dakari Johnson
Aaron White
Marcus Eriksson
Tyler Harvey
Satnam Singh Bhamara
Sir'Dominic Pointer
Dani Díez
Cady Lalanne
Branden Dawson
Nikola Radičević
J. P. Tokoto
Dimitrios Agravanis
Luka Mitrović
Retrieved from "https://en.wikipedia.org/w/index.php?title=Larry_Nance_Jr.&oldid=842946062"
Categories:
1993 births
Living people
African-American basketball players
Basketball players from Ohio
Centers (basketball)
Cleveland Cavaliers players
Los Angeles Lakers draft picks
Los Angeles Lakers players
Power forwards (basketball)
Sportspeople from Akron, Ohio
Wyoming Cowboys basketball players
Hidden categories:
Wikipedia pending changes protected pages
Articles which use infobox templates with no data rows
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Languages
العربية
Deutsch
Español
فارسی
Français
Italiano
עברית
日本語
Polski
Português
Русский
Türkçe
Українська
Volapük
中文
6 more
Edit links
This page was last edited on 25 May 2018, at 19:19.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: Page protected with pending changes level 1

values: All edits by unregistered and new users are subject to review prior to becoming visible to unregistered users

values: firstHeading firstHeading en

values: siteSub noprint

attrs: class src alt title

values: Changes must be reviewed before being displayed on this page.

attrs: id class src style alt

attrs: class href

value: i

attrs: id style class

values: flaggedrevs_short flaggedrevs_stable_synced plainlinks noprint nomobile

values: jump-to-nav mw-jump

values: Larry Nance Jr. (38817215320) (cropped).jpg

values: text-align:center;background-color:#6F263D;color:#FFFFFF;-moz-box-shadow: inset 2.5px 2.5px 0 #FFB81C, inset -2.5px -2.5px 0 #FFB81C; -webkit-box-shadow: inset 2.5px 2.5px 0 #FFB81C, inset -2.5px -2.5px 0 #FFB81C; box-shadow: inset 2.5px 2.5px 0 #FFB81C, inset -2.5px -2.5px 0 #FFB81C;

values: Edit section: High school and college career

values:
headerSort
0
columnheader button
Sort ascending

values:
Minutes per game
border-bottom:1px dotted

values:
Field goal percentage
border-bottom:1px dotted

values:
3-point field-goal percentage
border-bottom:1px dotted

values:
Free-throw percentage
border-bottom:1px dotted

values:
Rebounds per game
border-bottom:1px dotted

values:
Assists per game
border-bottom:1px dotted

values:
Steals per game
border-bottom:1px dotted

values:
Blocks per game
border-bottom:1px dotted

values:
Points per game
border-bottom:1px dotted

values: 2011–12 NCAA Division I men's basketball season

values: 2012–13 NCAA Division I men's basketball season

values: 2013–14 NCAA Division I men's basketball season

values: 2014–15 NCAA Division I men's basketball season

values:
wikitable sortable jquery-tablesorter
font-size:95%; text-align:right;

values: Edit section: Los Angeles Lakers (2015–2018)

values: Edit section: Cleveland Cavaliers (2018–present)

values: background-color: #F2F2F2; border: 1px solid #AAAAAA;

values: background-color: #F2F2F2; border: 1px solid black;

values:
toccolours
font-size: 90%; white-space: nowrap;

values: display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle

values: margin:0.5em 0 0.5em 1em;border:solid #aaa 1px

values:
collapseButton0
#
color: rgb(255, 255, 255);

values: ;background-color:#6F263D;color:#FFFFFF;-moz-box-shadow: inset 2px 2px 0 #FFB81C, inset -2px -2px 0 #FFB81C; -webkit-box-shadow: inset 2px 2px 0 #FFB81C, inset -2px -2px 0 #FFB81C; box-shadow: inset 2px 2px 0 #FFB81C, inset -2px -2px 0 #FFB81C;;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;

values: Template:Cleveland Cavaliers current roster

values: Template talk:Cleveland Cavaliers current roster

values: nowraplinks collapsible autocollapse navbox-inner

values:
row
navbox-group
width:1%;text-align: center;

values: Category:Wyoming Cowboys basketball players

values: Category:Wikipedia pending changes protected pages

values: Category:Articles which use infobox templates with no data rows

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Larry_Nance_Jr.
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: لاري نانس جونيور – Arabic

values: لری نانس جونیور – Persian

values:
interlanguage-link interwiki-fa
display: none;

values:
interlanguage-link interwiki-it
display: none;

values: לארי נאנס הבן – Hebrew

values:
interlanguage-link interwiki-he
display: none;

values: ラリー・ナンス・ジュニア – Japanese

values:
interlanguage-link interwiki-pl
display: none;

values: Нэнс, Ларри (младший) – Russian

values: Ларрі Ненс (молодший) – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values:
interlanguage-link interwiki-vo
display: none;

values: 小賴瑞·南斯 – Chinese

values: All languages (initial selection from common choices by you and others)

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Larry_Nance_Jr rootpage-Larry_Nance_Jr skin-vector action-view