Python For GCSE
Searching Algorithms

In order to make these exercises interesting, you can use the following list. It has 722 music artists, all written in upper case and not in alphabetical order.

artists = ['PET SHOP BOYS', 'RAMSEY LEWIS', 'POLARIZED', 'THERAPY',
           'TOM VEK', 'STATUS QUO', 'SHIRLEY COLLINS', 'DEXYS MIDNIGHT RUNNERS',
           'ANOTHER STORY', 'THE TROGGS', 'ARCHIE BRONSON OUTFIT',
           'ELVIS COSTELLO', 'DILLINGER', 'DAVID BOWIE', 'SIMPLE MINDS',
           'ROSE ROYCE', 'BARRET STRONG', 'HARD-FI', 'THIRTEEN SENSES',
           'EXTREME', 'PWEI', 'BONNIE DOBSON', 'CURVE', 'SUBWAYS', 'ABBA',
           'CRAIG ARMSTRONG', 'DODGY', 'FRANZ FERDINAND', 'GRAND DRIVE',
           'PETER BRUNTNELL', 'JONATHAN RICHMNA & THE MODERN LOVERS',
           'YAZOO', 'ARCTIC MONKEYS', 'CHRIS BELL', 'LLOYD COLE AND THE COMMOTIONS',
           'KINGDOM COME', 'THE OFFSPRING', 'MANSUN', 'CHIKINKI', 'TOTO', 'JOY DIVISION',
           'BLACK SABBATH', 'FIELDS OF THE NEPHILIM', 'THE SMALL FACES',
           'PETE WILLIAMS', 'WONDER STUFF', 'DARDEN SMITH', 'THE FLOWERPOT MEN',
           'GARY JULES', 'THE KILLS', 'THE JESUS & MARY CHAIN', 'FAIRPORT CONVENTION',
           'THE DEAD KENNEDYS', 'THE SLITS', 'MUDDY WATERS', 'BETH GIBBONS & RUSTIN MAN',
           'KULA SHAKER', 'JOHN RENBOURN', 'STING', 'LAURA VEIRS', 'CATATONIA', 'RADIOHEAD',
           'STARSAILOR', 'UNPOC', 'DOVES', 'MORCHEEBA', 'PRINCE', 'NINA SIMONE',
           'AZTEC CAMERA', 'GODSMACK', 'MOLOKO', 'WILLIE NELSON', 
           'ELMORE JAMES & HIS BROOM DUSTERS', 'THE STREETS', 'COUNTRY JOE & THE FISH',
           'PETE SEEGER', 'THE DATSUNS', 'DAMIEN RICE', 'JULIE LONDON', 'THE REDSKINS', 
           'TOM ROBINSON BAND', 'NEW YORK DOLLS', 'HAWKWIND', 'ZODIAC MINDWARP',
           'THE SAINTS', 'BOOKER T & THE MGS', 'SUB CIRCUS', 'RAINBOW', 'SUM 41', 
           'MAGNET', 'MEAT LOAF', 'LEONARD COHEN', 'CAST', 'GERRY & THE PACEMAKERS', 
           'MAROON 5', 'SIOUXSIE AND THE BANSHEES', 'STEREPHONICS', 'SPEAR OF DESTINY',
           'PENETRATION', 'KINGS OF LEON', 'THE MONOCHROME SET', 'STIFF LITTLE FINGERS',
           'EVAN DANDO', 'STEVIE WONDER', 'ASH', 'SONS AND DAUGHTERS', 'ARETHA FRANKLIN', 
           'THE PRETENDERS', 'HOPE', 'SUPERGRASS', 'SECRET AFFAIR', 'THE LOVIN SPOONFUL',
           'NICKLEBACK', 'PIXIES', 'CREAM', 'NORMA WATERSON', 'ERASURE', 'THE ASSOCIATES',
           'THE WRENS', 'JUNIOR WALKER & THE ALL STARS', 'RAM JAM', 'DANIEL BEDINGFIELD',
           'STEREOPHONICS', 'BACHMAN TURNER OVERDRIVE', 'BONNIE TYLER', 'SIMON & GARFUNKEL',
           'MASSIVE ATTACK', 'CLINIC', 'THE CARDIGANS', 'BRIAN FERRY', 'SHARON SHANNON',
           'STELLASTARR*', 'PAUL WELLER', 'CLANNAD', 'KAISER CHIEFS', 'RILO KILEY',
           'BEATS INTERNATIONAL', 'THE DEPARTURE', 'PAT BENATAR', 'MAX TUNDRA',
           'ERIC CARMEN', 'DAVEY GRAHAM', 'BILLY IDOL', 'HUMAN LEAGUE', 'MADONNA',
           'PJ HARVEY', 'OTHERS', 'BOB MARLEY', 'THE COOPER TEMPLE CLAUSE', 'MUSE',
           'DAMIEN DEMPSEY', 'THE SUGARCUBES', 'THE DAMNED', 'ELECTRIC SIX',
           'WONDERMINTS', 'ALTERED IMAGES', 'FAITH NO MORE', 'DIDO', 'MAGNUM', 
           'THE MISUNDERSTOOD', 'JOBRIATH', 'NAZARETH', 'REZILLOS', 'JANIS IAN',
           'CANNED HEAT', 'JAN & DEAN', 'DANNY WILSON', 'THE DOORS', 'BEBEL GILBERTO',
           'THE DELGADOS', 'RUSH', 'SKID ROW', 'BOB DYLAN', 'THE ANIMALS',
           'THE HOLLIES', 'COLDPLAY', 'FREE', 'THE DETROIT SPINNERS', 'CHICAGO',
           'THE WHO', 'MANFRED MANN', 'KATHRYN WILLIAMS', 'AMY WINEHOUSE', 
           'CHELSEA', 'PETER SARSTEDT', 'THE MARVELETTES', 'JOHN PRINE',
           'THE ISLEY BROTHERS', 'BRENDAN BENSON', 'DON MACLEAN', 'SOUNDGARDEN',
           'RAZORLIGHT', 'LONGVIEW', 'JULIAN COPE', 'FUTURE KINGS OF SPAIN',
           'SPIN DOCTORS', 'IAN DURY & THE BLOCKHEADS', 'THE SCORPIONS', 'THE ASSEMBLY',
           'NILSSON', 'RORY MCLEOD', 'DIO', 'FUGEES (REFUGEE CAMP)', 'JIMMY SOMERVILLE',
           'THE WHITE STRIPES', 'THE BLUESKINS', 'THE SHADOWS', 'FREDA PAYNE', 'FOUR TET',
           'KATE BUSH', 'MOTORHEAD', 'FEEDER', 'XTC', 'NINA NASTASIA', 'PORTISHEAD',
           'THE RED HOT CHILI PEPPERS', 'THE DELAYS', 'LOTUS EATERS', 'THE HERD',
           'BIG STAR', 'PRODIGY', 'BERT JANSCH', 'CARTER USM', 'THE ONLY ONES', 'OASIS',
           'THE VELVET UNDERGROUND', 'JOHN MARTYN', 'BROKEN ENGLISH', 'ELBOW', 'SEX PISTOLS',
           'LAURYN HILL', 'LOUDON WAINWRIGHT III', 'JEFF BUCKLEY', 'JOHN COOPER CLARKE',
           'KID SYMPHONY', 'THE STRANGLERS', 'ROBERT PLANT', 'MYLO', 'UFO', 
           'THE COCTEAU TWINS', 'MITCH BENN', 'THE HIVES', 'THE FUTUREHEADS', 'FAITHLESS',
           'KT TUNSTALL', 'THE BYRDS', 'TEARS FOR FEARS', 'PROPAGANDA',
           'MANIC STREET PREACHERS', 'PHIL LYNOTT', 'THE STYLE COUNCIL', 'NENA',
           'JOAN BAEZ', 'INXS', 'BRIGHT EYES', 'VISAGE', 'SIMON DUPREE & THE BIG SOUND',
           'DURAN DURAN', 'ELLIOTT SMITH', 'JOURNEY', 'THE LEVELLERS', 'SHAMEN',
           'THE GO! TEAM', 'THE RAMONES', 'SPIRIT', 'PROCOL HARUM', 'CURTIS MAYFIELD',
           'TURIN BRAKES', 'RICHARD THOMPSON', 'SHAM 69', 'ART OF NOISE', 'BESSIE SMITH',
           'SAINT ETIENNE', 'FUNKADELIC', 'BELOUIS SOME', 'DUANE EDDY', 'BLANCMANGE',
           'GRANDMASTER FLASH', 'THE LEMONHEADS', 'SPECIALS', 'EMMANUEL JAL',
           'CHAIRMAN OF THE BOARD', 'GARNET MIMMS', 'SLEEPER',
           'BIG BROTHER & THE HOLDING COMPANY', 'DOGS DIE IN HOT CARS',
           'THE EVERLY BROTHERS', 'JACKIE LEVEN', 'GARY MOORE', 'X RAY SPEX', 'I AM KLOOT',
           'BIG AUDIO DYNAMITE', 'THE INCREDIBLE STRING BAND', 'FOREIGNER', 'THE WANNADIES',
           'WOODY GUTHRIE', 'THE ICICLE WORKS', 'TONY MCRAE', 'T REX', 'GREEN DAY', 'KEANE',
           'JOE WALSH', 'WEEZER', 'AMADOU & MARIAM', 'CHUCK BERRY', 'BLUE OYSTER CULT',
           'CULTURE CLUB', 'SILVER JEWS', 'THE CHORDS', 'SUEDE', 'BETH ORTON', 'THE BANGLES',
           'TOMMY JAMES & THE SHONDELLS', 'THE SWEET', 'THE BONZO DOG DOO DAH BAND',
           'FOO FIGHTERS', 'YNGWIE MALMSTEEN', 'EVA CASSIDY', 'FURNITURE', 'THE STROKES',
           'BABYSHAMBLES', 'PAUL YOUNG', 'THE FARM', 'POP WILL EAT ITSELF', 'AMBERSHADES',
           'THE WATERSONS', 'THE SHIRELLES', 'LED ZEPPELIN', 'BLINK 182', 'ELASTICA',
           'THE BRAVERY', 'KILLING JOKE', 'SADE', 'GEORGE AND ANTONY',
           'HALF MAN HALF BISCUIT', 'FICTION FACTORY', 'RACHEL MARI KIMBER',
           'INSPIRAL CARPETS', 'HOOD', 'DICK GAUGHAN', 'DEACON BLUE', 'ORBITAL',
           'THE POGUES', 'JETHRO TULL', 'BUKKA WHITE', 'STEPPENWOLF', 'THE SONICS',
           'HARRY THE HIPSTER GIBSON', 'THE MAMAS & THE PAPAS', 'RYAN ADAMS & THE CARDINALS',
           'THE BOO RADLEYS', 'SQUIRE', 'HEAVEN 17', 'THE TEMPTATIONS', 'LYNYRD SKYNYRD',
           'RYAN ADAMS', 'CRYSTAL GAYLE', 'THE SEARCHERS', 'DEEP PURPLE', 'RON SEXSMITH',
           'ELECTRIC SOFT PARADE', 'THE DUBLINERS', 'ADAM & THE ANTS', 'CAPTAIN BEEFHEART',
           'SOFT CELL', 'JOHN LENNON', 'GENESIS', 'LUCIANO PAVAROTTI',
           'NO ME PISES QUE LLEVO CHANCLAS', 'JOSEPH ARTHUR', 'B.R.M.C.', 'JIMI HENDRIX',
           'INTERPOL', 'LONNIE DONEGAN', 'JEFF BECK', 'IDLEWILD', 'KRAFTWERK',
           'THE FLYING LIZARDS', 'FOCUS', 'THE CURE', 'LOVE', 'THE BEES',
           'SCOTT MCKENZIE', 'MONSTER MAGNET', 'WILSON PICKETT', 'EURYTHMICS',
           'ROBERT JOHNSON', 'HALLOWEEN ALASKA', 'DAVID GRAY', 'SIGUR ROS', 'BRYAN ADAMS',
           'PULP', 'THE SPENCER DAVIS GROUP', 'TRACY CHAPMAN', 'ALL ABOUT EVE',
           'GEORGE MICHAEL', 'LOU REED', 'BOSTON', 'PUBLIC IMAGE LTD', 'SUZANNE VEGA',
           'EXPLOSIONS IN THE SKY', 'HELL IS FOR HEROES', 'VAN HALEN',
           'CHARLOTTE HATHERLEY', 'OWEN HAND', 'BLUR', 'STEREO MCS', 'WESTWORLD',
           'BJORK', 'THE RUTS', 'JIMMY NAIL', 'THE DARKNESS', 'DAVID AXELROD', 'ROBERT WYATT',
           'HOUSE OF LOVE', 'RICHARD HELL AND THE VOIDOIDS', 'THE THE', 'OLIVER',
           'SILLY SISTERS', 'LIVE', 'THE PRETTY THINGS', 'THE CORAL', 'DR FEELGOOD',
           'ECHO & THE BUNNYMEN', 'THE MAGIC NUMBERS', 'BILLY BRAGG', 'GUN', 'CHET BAKER',
           'ADEM', 'CAPERCAILLIE', 'MIDGE URE', 'FONTELLA BASS', 'LEAD BELLY',
           'SMOKEY ROBINSON & THE MIRACLES', 'PSYCHEDELIC FURS', 'LINTON KWESI JOHNSON',
           'THE DISTILLERS', 'PAVEMENT', 'DEPECHE MODE', 'BABYBIRD', 'MY CHEMICAL ROMANCE',
           'TPAU', 'THE SUPREMES', 'EWAN MACCOLL', 'JAPAN', 'BELINDA CARLISLE', 'REEF',
           'BOX TOPS', 'THE CHARLATANS', 'SPARKS', 'STEPHEN TIN TIN DUFFY',
           'THE VELVELETTES', 'MARTHA WAINWRIGHT', 'CLEARLAKE', 'THE FLYS', 'THE CHI-LITES',
           'THE ORDINARY BOYS', 'NAT ADDERLY', 'THE MUSIC', 'TALK TALK', 'JAMES', 'ABC',
           'SISTERS OF MERCY', 'JOSH ROUSE', 'R.E.M.', 'FLEETWOOD MAC', 'DOBIE GRAY',
           'SCOTT WALKER', 'THE MEMBERS', 'PRIMITIVES', 'WYCLEF JEAN', 'CHINA CRISIS',
           'DE DANNAN', 'THE SWINGING BLUE JEANS', 'WILLY MASON', 'PINK FLOYD',
           'JOHNNY CASH', 'THE KINKS', 'ROY BUCHANAN', 'THE PLASTIC ONO BAND',
           'SUFJAN STEVENS', 'KIM WILDE', 'DOC WATSON & CLARENCE ASHLEY', 'UNKNOWN ARTIST',
           'THE YARDBIRDS', 'BOOMTOWN RATS', 'BELLE & SEBASTIAN', 'TONES ON TAIL',
           'FRANCOISE HARDY', 'KIRSTY MACCOLL', 'ME', 'THE MASH', 'PRIMAL SCREAM', 'THE FALL',
           'SPIRITUALIZED', 'FRIJID PINK', 'GEORGIA SATELLITES', 'THE BREEDERS',
           'DREAM ACADEMY', 'ODETTA', 'SACK', 'THE PASSIONS', 'JACK JOHNSON', 'ARTHUR CONLEY',
           'BOW WOW WOW', 'GIORGIO MORODER & PHIL OAKEY', 'ATHLETE', 'NICK DRAKE', 'VAN MORRISON',
           'CULTURE', 'NO DOUBT', 'SUPERTRAMP', 'THE SMITHS', 'KUBB', 'CORNERSHOP', 'THE ZOMBIES',
           'MINISTRY', 'THE DRAMATICS', 'THE EAGLES', 'THE JAM', 'THE SKIDS', 'GENERATION X',
           'SERAFIN', 'THE FLAMIN GROOVIES', 'LAMBCHOP', 'THE BEATLES', 'RENAISSANCE',
           'FRANKIE GOES TO HOLLYWOOD', 'GLEN CAMPBELL', 'PP ARNOLD', 'EMILIANA TORRINI',
           'JILTED JOHN', 'LOVE & ROCKETS', 'OCEAN COLOUR SCENE', 'THE MOVE', 'K.D. LANG',
           'THE MIGHTY HANNIBAL', 'REO SPEEDWAGON', 'THE CULT', 'FUN BOY THREE', 'THIN LIZZY',
           'JACKSON BROWNE', 'SMALL WORLD', 'LONG PIGS', 'BAUHAUS', 'THE ZUTONS', 'TINARIWEN',
           'SNOW PATROL', 'CLASSIX NOUVEAU', 'MERCURY REV', 'THE UNDERTONES', 'CHICKEN SHACK',
           'BLONDIE', 'ZERO 7', 'FERNHILL', 'THE BELOVED', 'DONOVAN', 'BLIND WILLIE JOHNSON', 
           'QUEEN', 'BOB & EARL', 'JESUS JONES', 'SPACEMEN 3', 'MARTHA REEVES & THE VANDELLAS',
           'ECHOBELLY', 'ULTRAVOX', 'REMMA', 'MALVINA REYNOLDS', 'BIFFY CLYRO', 'THE ORB',
           'STEPHEN MALKMUS & THE JICKS', 'OMD', 'GORILLAZ', 'NEIL FINN', 'THE LAS', 
           'SCRITTI POLITTI', 'STEPHEN FRETWELL', 'MICHELLE SHOCKED', 'JUDAS PRIEST',
           'TERENCE TRENT DARBY', 'PRODUCT G&B', 'THE KILLERS', 'MIKE OLDFIELD',
           'PONY CLUB', 'JOHN FAHEY', 'BUZZCOCKS', 'UB40', 'RAGE AGAINST THE MACHINE',
           'STEVIE RAY VAUGHAN AND DOUBLE TROUBLE', 'JAMES YORKSTON AND THE ATHLETES',
           'MY RED CELL', 'MADNESS', 'FOUR TOPS', 'IGGY POP', 'ORANGE JUICE', 'DEVO',
           'MAGAZINE', 'SEBADOH', 'THE BLUEBELLS', 'GRANT LEE PHILLIPS', 'VIOLENT FEMMES',
           'PIG BAG', 'THE WEDDING PRESENT', 'THE STONE ROSES', 'CYNDI LAUPER',
           'SANTO & JOHNNY', 'NEW ORDER', 'JAMES BOOKER', 'NORAH JONES', 'BLOC PARTY',
           'MEN AT WORK', 'JAMES BROWN', 'NICK CAVE & THE BAD SEEDS', 'DAVE EDMUNDS',
           'THE LAMBRETTAS', 'PROCLAIMERS', 'THOMAS DOLBY', 'LAURA CANTRELL', 'LADYTRON', 
           'SUGABABES', 'THE SMASHING PUMPKINS', 'EDDIE FLOYD', 'DEAN TAYLOR', 'MARTIN GRECH',
           'THE FLAMING LIPS', 'SHED SEVEN', 'JOE COCKER', 'CROWDED HOUSE',
           'THE DANDY WARHOLS', 'THE VINES', 'THE POLICE', 'THE CREATION', 'THE VON BONDIES',
           'THE VERVE', 'GENE', 'MARILLION', 'MEW', 'ORENDA FINK', 'YELLO', 'CHRIS SPEDDING',
           'JEFFERSON AIRPLANE', 'KASABIAN', 'BILLIE HOLIDAY', 'ABRAHAM', 'LUDUS',
           'RAMMSTEIN', 'RED LORRY YELLOW LORRY', 'PETER GABRIEL', 'MOBY',
           'ELIZA CARTHY', 'THE SUBWAYS', 'THE MISSION', 'MERTON PARKAS', 'THE CLASH',
           'URIAH HEEP', 'AQUALUNG', 'ROY ORBISON', 'JOSH WHITE', 'AIR', 'GARY NUMAN',
           'THE CRANBERRIES', 'THE FRATERNITY OF MAN', 'WHEATUS', 'PURPLE HEARTS',
           'SPANDAU BALLET', 'THE BIRTHDAY PARTY', 'SHOWSTOPPERS', 'SUPER FURRY ANIMALS',
           'PREFAB SPROUT', 'RAYMONDE', 'CLIFF BENNET & THE REBEL ROUSERS', 'TUBEWAY ARMY',
           'THE TEARDROP EXPLODES', 'NIRVANA', 'TRAVIS', 'RUFUS WAINWRIGHT', 'WIRE',
           'SUB POP SUNDAY', 'RICHIE HAVENS', 'EMBRACE', 'THE FINN BROTHERS', 'TOMORROW',
           'KATE RUSBY', 'HOWLIN WOLF', 'GANG OF FOUR', 'LITTLE RICHARD',
           'FUNERAL FOR A FRIEND', 'THE BLUETONES', 'QUEENS OF THE STONE AGE',
           'FLYING BURRITO BROS', 'OTIS REDDING', 'MB2', 'JOHN FRED & HIS PLAYBOY BAND',
           'JANES ADDICTION', 'THE SOUP DRAGONS', 'THE LIBERTINES', 'THE TURTLES',
           'GENE LOVES JEZEBEL', 'LEMON JELLY', 'THE CREATURES', 'CHRIS FARLOWE', 
           'OZZY OSBOURNE', 'THE BLOW MONKEYS', 'BILL WITHERS', 'MARVIN GAYE', 'U2',
           'THE RASMUS', 'TIM BUCKLEY', 'THE NASHVILLE TEENS', 'THE BEACH BOYS', 'MONTROSE',
           'NEIL YOUNG', 'PLACEBO', 'JOE STRUMMER & THE MESCALEROS', 'HAL',
           'NEIL HANNON & YANN TIERSEN', 'DIONNE WARWICK', 'DAVE VAN RONK', 'HANK WILLIAMS',
           'MY MORNING JACKET', 'FUTURE SOUND OF LONDON', 'MAXIMO PARK', 'NEDS ATOMIC DUSTBIN']

Linear Search

When the items we are searching through are not in any order, we have to look at them one at a time. We can stop when we find what we are looking for. If the item we are looking for is not in the list, we may have to search through the entire list.

Here is pseudocode for a linear search function that returns the index where the item is found or -1 if it is not found. The parameters are the list we are searching (lst) and the item we are looking to find (item).

FUNCTION linear(lst, item)
   current = 0
   maxitem = LENGTH of lst
   WHILE current <= maxitem
      IF lst[current]==item THEN
         return current
      END IF
      current = current + 1
   END WHILE
   return -1
END FUNCTION

Do something like this to test. You won't get the same number as the list is shuffled. Remember to use upper case for the artist name.

Binary Search

When the collection of items we are searching is in order, we can use a binary search. This algorithms works by comparing the item with the middle of the list. If the item should come before the item in the middle, we can stop looking in the top half of the list. We repeat that process of halving the list until we find what we are looking for or realise it is not there.

In comparison to the linear search, the binary search is quick. 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.

The first thing we need is to put our list in order. Fortunately, Python has a built-in sorting method. Copy the list from above into a new file and then add the following line to get it in order,

artists = sorted(artists)

Here is some pseudocode for a binary search function for you to implement and test. It includes an output statement that will help you see how the binary search is working. This would be removed once you understand what is going on. As with the linear search, it is meant to return the index of the item or -1 if it is not in the list.

FUNCTION binseearch(lst, item)
   first = 0
   last = len(lst)-1
   found = False
   WHILE first<=last AND NOT found
      midpoint = (first + last) DIV 2
      OUTPUT "Compare", item, "with", lst[midpoint]
      IF lst[midpoint]==item THEN
         found = True
      ELSE
         IF item<lst[midpoint] THEN
            last = midpoint - 1
         ELSE
            first = midpoint + 1
         END IF
      END IF
   END WHILE
   IF found THEN
      return midpoint
   ELSE
      return -1
   END IF
END FUNCTION