Visual C# 2005 Guide
Binary Search

The linear search is not particularly efficient when searching a sorted array. The binary search works by comparing the item you want to find with the item stored at the midpoint of the list. If the item should come before the item at the midpoint, the second half of the list need not be searched. The midpoint of the the first part of the list would then be compared with the search item and a similar process followed. By comparing the item with ever-shrinking lists, the binary search requires very few comparisons to either find an item or establish that it is not in the list.

The following program uses a recursive procedure for binary searching. The beginning of the program is a large array of artists for searching.

static string[] artists = {"22-20's","999","ABBA","ABC","Abraham","Adam & The Ants","Adem","Air","Alien Sex Fiend","All About Eve","Altered Images","Amadou & Mariam","Ambershades","Amy Winehouse","Another Story","Aqualung","Archie Bronson Outfit","Aretha Franklin","Art Of Noise","Arctic Monkeys","Arthur Conley","Ash","Athlete","Aztec Camera","B.R.M.C.","Babybird","Babyshambles","Bachman Turner Overdrive","Barret Strong","Bauhaus","Beats International","Bebel Gilberto","Belinda Carlisle","Belle & Sebastian","Belouis Some","Bert Jansch","Bessie Smith","Beth Gibbons & Rustin Man","Beth Orton","Biffy Clyro","Big Audio Dynamite","Big Brother & The Holding Company","Big Star","Bill Withers","Billie Holiday","Billy Bragg","Billy Idol","Bjork","Black Sabbath","Blancmange","Blind Willie Johnson","Blink 182","Bloc Party","Blondie","Blue Oyster Cult","Blur","Bob & Earl","Bob Dylan","Bob Marley","Bonnie Dobson","Bonnie Tyler","Booker T & The MGs","Boomtown Rats","Boston","Bow Wow Wow","Box Tops","Brendan Benson","Brian Ferry","Bright Eyes","Broken English","Bryan Adams","Bukka White","Buzzcocks","Canned Heat","Capercaillie","Captain Beefheart","Carter USM","Cast","Catatonia","Chairman Of The Board","Charlotte Hatherley","Chelsea","Chet Baker","Chicago","Chicken Shack","Chikinki","China Crisis","Chris Bell","Chris Farlowe","Chris Spedding","Chuck Berry","Clannad","Classix Nouveau","Clearlake","Cliff Bennet & The Rebel Rousers","Clinic","Coldplay","Cornershop","Country Joe & the Fish","Craig Armstrong","Cream","Crowded House","Crystal Gayle","Culture","Culture Club","Curtis Mayfield","Curve","Cyndi Lauper","Damien Dempsey","Damien Rice","Daniel Bedingfield","Danny Wilson","Darden Smith","Dave Edmunds","Dave Van Ronk","Davey Graham","David Axelrod","David Bowie","David Gray","De Dannan","Deacon Blue","Dean Taylor","Deep Purple","Depeche Mode","Devo","Dexy's Midnight Runners","Dick Gaughan","Dido","Dillinger","Dio","Dionne Warwick","Dobie Gray","Doc Watson & Clarence Ashley","Dodgy","Dogs Die In Hot Cars","Don MacLean","Donovan","Doves","Dr Feelgood","Dream Academy","Duane Eddy","Duran Duran","Echo & the Bunnymen","Echobelly","Eddie Floyd","Elastica","Elbow","Electric Six","Electric Soft Parade","Eliza Carthy","Elliott Smith","Elmore James & His Broom Dusters","Elvis Costello","Embrace","Emiliana Torrini","Emmanuel Jal","Erasure","Eric Carmen","Eurythmics","Eva Cassidy","Evan Dando","Ewan MacColl","Explosions In the Sky","Extreme","Fairport Convention","Faith No More","Faithless","Feeder","Fernhill","Fiction Factory","Fields Of The Nephilim","Fleetwood Mac","Flying Burrito Bros","Focus","Fontella Bass","Foo Fighters","Foreigner","Four Tet","Four Tops","Francoise Hardy","Frankie Goes To Hollywood","Franz Ferdinand","Freda Payne","Free","Frijid Pink","Fugees (Refugee Camp)","Fun Boy Three","Funeral for a Friend","Funkadelic","Furniture","Future Kings Of Spain","Future Sound of London","Gang Of Four","Garnet Mimms","Gary Jules","Gary Moore","Gary Numan","Gene","Gene Loves Jezebel","Generation X","Genesis","George And Antony","George Michael","Georgia Satellites","Gerry & The Pacemakers","Giorgio Moroder & Phil Oakey","Glen Campbell","Godsmack","Gorillaz","Grand Drive","Grandmaster Flash","Grant Lee Phillips","Green Day","Gun","Hal","Half Man Half Biscuit","Halloween Alaska","Hank Williams","Hard-Fi","Harry The Hipster Gibson","Hawkwind","Heaven 17","Hell Is For Heroes","Hood","Hope","House of Love","Howlin' Wolf","Human League","I Am Kloot","Ian Dury & The Blockheads","Idlewild","Iggy Pop","Inspiral Carpets","Interpol","INXS","Jack Johnson","Jackie Leven","Jackson Browne","James","James Booker","James Brown","James Yorkston And The Athletes","Jan & Dean","Jane's Addiction","Janis Ian","Japan","Jeff Beck","Jeff Buckley","Jefferson Airplane","Jesus Jones","Jethro Tull","Jilted John","Jimi Hendrix","Jimmy Nail","Jimmy Somerville","Joan Baez","Jobriath","Joe Cocker","Joe Strummer & The Mescaleros","Joe Walsh","John Cooper Clarke","John Fahey","John Fred & His Playboy Band","John Lennon","John Martyn","John Prine","John Renbourn","Johnny Cash","Jonathan Richmna & The Modern Lovers","Joseph Arthur","Josh Rouse","Josh White","Journey","Joy Division","Judas Priest","Julian Cope","Julie London","Junior Walker & The All Stars","k.d. Lang","Kaiser Chiefs","Kasabian","Kate Bush","Kate Rusby","Kathryn Williams","Keane","Kid Symphony","Killing Joke","Kim Wilde","Kingdom Come","Kings of Leon","Kirsty MacColl","Kraftwerk","KT Tunstall","Kubb","Kula Shaker","Ladytron","Lambchop","Laura Cantrell","Laura Veirs","Lauryn Hill","Lead Belly","Led Zeppelin","Lemon Jelly","Leonard Cohen","Linton Kwesi Johnson","Little Richard","Live","Lloyd Cole And The Commotions","Long Pigs","Longview","Lonnie Donegan","Lostprophets","Lotus Eaters","Lou Reed","Loudon Wainwright III","Love","Love & Rockets","Luciano Pavarotti","Ludus","Lynyrd Skynyrd","Madness","Madonna","Magazine","Magnet","Magnum","Malvina Reynolds","Manfred Mann","Manic Street Preachers","Mansun","Marillion","Maroon 5","Martha Reeves & The Vandellas","Martha Wainwright","Martin Grech","Marvin Gaye","Massive Attack","Max Tundra","Maximo Park","MB2","Me","Meat Loaf","Men At Work","Mercury Rev","Merton Parkas","Mew","Michelle Shocked","Midge Ure","Mike Oldfield","Ministry","Mitch Benn","Moby","Moloko","Monster Magnet","Montrose","Morcheeba","Motorhead","Muddy Waters","Muse","My Chemical Romance","My Morning Jacket","My Red Cell","Mylo","Nat Adderly","Nazareth","Ned's Atomic Dustbin","Neil Finn","Neil Hannon & Yann Tiersen","Neil Young","Nena","New Order","New York Dolls","Nick Cave & the Bad Seeds","Nick Drake","Nickleback","Nilsson","Nina Nastasia","Nina Simone","Nirvana","No Doubt","No Me Pises Que Llevo Chanclas","Norah Jones","Norma Waterson","Oasis","Ocean Colour Scene","Odetta","Oliver","OMD","Orange Juice","Orbital","Orenda Fink","Others","Otis Redding","Owen Hand","Ozzy Osbourne","Pat Benatar","Paul Weller","Paul Young","Pavement","Penetration","Pet Shop Boys","Pete Seeger","Pete Williams","Peter Bruntnell","Peter Gabriel","Peter Sarstedt","Phil Lynott","Pig Bag","Pink Floyd","Pixies","PJ Harvey","Placebo","Polarized","Pony Club","Pop Will Eat Itself","Portishead","PP Arnold","Prefab Sprout","Primal Scream","Primitives","Prince","Proclaimers","Procol Harum","Prodigy","Product G&B","Propaganda","Psychedelic Furs","Public Image Ltd","Pulp","Purple Hearts","PWEI","Queen","Queens Of The Stone Age","R.E.M.","Rachel Mari Kimber","Radiohead","Rage Against the Machine","Rainbow","Ram Jam","Rammstein","Ramsey Lewis","Raymonde","Razorlight","Red Lorry Yellow Lorry","Reef","Remma","Renaissance","REO Speedwagon","Rezillos","Richard Hell And The Voidoids","Richard Thompson","Richie Havens","Rilo Kiley","Robert Johnson","Robert Plant","Robert Wyatt","Ron Sexsmith","Rory McLeod","Rose Royce","Roy Buchanan","Roy Orbison","Rufus Wainwright","Rush","Ryan Adams","Ryan Adams & The Cardinals","Sack","Sade","Saint Etienne","Santo & Johnny","Scott McKenzie","Scott Walker","Scritti Politti","Sebadoh","Secret Affair","Serafin","Sex Pistols","Sham 69","Shamen","Sharon Shannon","Shed Seven","Shirley Collins","Showstoppers","Sigur Ros","Silly Sisters","Silver Jews","Simon & Garfunkel","Simon Dupree & The Big Sound","Simple Minds","Siouxsie And The Banshees","Sisters Of Mercy","Skid Row","Sleeper","Small World","Smokey Robinson & The Miracles","Snow Patrol","Soft Cell","Sons And Daughters","Soundgarden","Spacemen 3","Spandau Ballet","Sparks","Spear Of Destiny","Specials","Spin Doctors","Spirit","Spiritualized","Squire","Starsailor","Status Quo","Stellastarr*","Stephen Fretwell","Stephen Malkmus & The Jicks","Stephen Tin Tin Duffy","Steppenwolf","Stereo MC's","Stereophonics","Sterephonics","Stevie Ray Vaughan And Double Trouble","Stevie Wonder","Stiff Little Fingers","Sting","Sub Circus","SUB POP SUNDAY","Subways","Suede","Sufjan Stevens","Sugababes","Sum 41","Super Furry Animals","Supergrass","Supertramp","Suzanne Vega","T Rex","Talk Talk","Tears For Fears","Terence Trent Darby","The Animals","The Assembly","The Associates","The Bangles","The Beach Boys","The Beatles","The Bees","The Beloved","The Birthday Party","The Blow Monkeys","The Bluebells","The Blueskins","The Bluetones","The Bonzo Dog Doo Dah Band","The Boo Radleys","The Bravery","The Breeders","The Byrds","The Cardigans","The Charlatans","The Chi-lites","The Chords","The Clash","The Cocteau Twins","The Cooper Temple Clause","The Coral","The Cranberries","The Creation","The Creatures","The Cult","The Cure","The Damned","The Dandy Warhols","The Darkness","The Datsuns","The Dead Kennedys","The Delays","The Delgados","The Departure","The Detroit Spinners","The Distillers","The Doors","The Dramatics","The Dubliners","The Eagles","The Everly Brothers","The Fall","The Farm","The Finn Brothers","The Flamin Groovies","The Flaming Lips","The Flowerpot Men","The Flying Lizards","The Flys","The Fraternity Of Man","The Futureheads","The Go! Team","The Herd","The Hives","The Hollies","The Icicle Works","The Incredible String Band","The Isley Brothers","The Jam","The Jesus & Mary Chain","The Killers","The Kills","The Kinks","The Lambrettas","The La's","The Lemonheads","The Levellers","The Libertines","The Lovin' Spoonful","The Magic Numbers","The Mamas & the Papas","The Marvelettes","The Mash","The Members","The Mighty Hannibal","The Mission","The Misunderstood","The Monochrome Set","The Move","The Music","The Nashville Teens","The Offspring","The Only Ones","The Orb","The Ordinary Boys","The Passions","The Plastic Ono Band","The Pogues","The Police","The Pretenders","The Pretty Things","The Ramones","The Rasmus","The Red Hot Chili Peppers","The Redskins","The Ruts","The Saints","The Scorpions","The Searchers","The Shadows","The Shirelles","The Skids","The Slits","The Small Faces","The Smashing Pumpkins","The Smiths","The Sonics","The Soup Dragons","The Spencer Davis Group","The Stone Roses","The Stranglers","The Streets","The Strokes","The Style Council","The Subways","The Sugarcubes","The Supremes","The Sweet","The Swinging Blue Jeans","The Teardrop Explodes","The Temptations","The The","The Troggs","The Turtles","The Undertones","The Velvelettes","The Velvet Underground","The Verve","The Vines","The Von Bondies","The Wannadies","The Watersons","The Wedding Present","The White Stripes","The Who","The Wrens","The Yardbirds","The Zombies","The Zutons","Therapy","Thin Lizzy","Thirteen Senses","Thomas Dolby","Tim Buckley","Tinariwen","Tom Robinson Band","Tom Vek","Tommy James & The Shondells","Tomorrow","Tones On Tail","Tony McRae","Toto","T'Pau","Tracy Chapman","Travis","Tubeway Army","Turin Brakes","U2","UB40","UFO","Ultravox","Unknown Artist","Unpoc","Uriah Heep","Van Halen","Van Morrison","Violent Femmes","Visage","War of the Worlds","Weezer","Westworld","Wheatus","Willie Nelson","Willy Mason","Wilson Pickett","Wire","Wonder Stuff","Wondermints","Woody Guthrie","Wyclef Jean","X Ray Spex","XTC","Yazoo","Yello","Yngwie Malmsteen","Zero 7","Zodiac Mindwarp"};

static void RecursiveBinarySearch(string item, int top, int bottom)
{
   int midpoint = (int)((top + bottom)/2);
   if (artists[midpoint]==item)
   {
      Console.WriteLine("Found item at index: {0}", midpoint);
   }
   else if (bottom > top)
   {
      Console.WriteLine("Search has failed");
   }
   else
   {
      if (String.Compare(artists[midpoint],item)<0)
      {
         RecursiveBinarySearch(item, top, midpoint+1);
      }
      else
      {
         RecursiveBinarySearch(item, midpoint -1, bottom);
      }
   }
}

static void Main(string[] args)
{
   string itemEntered;
   Console.Write("Enter the name of an artist: ");
   itemEntered = Console.ReadLine();
   RecursiveBinarySearch(itemEntered, artists.GetLength(0) - 1, 0);
   Console.ReadLine();
}

Having A Go

  1. In a list of 2n items, the binary search should require no more than n+1 comparisons to determine either the location of the item in the list or that it is not in the list. Mess around with the example program so that it will tell you each time the search item is compared with an item in the array.