{"id":150,"date":"2023-06-11T20:12:03","date_gmt":"2023-06-11T20:12:03","guid":{"rendered":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?page_id=150"},"modified":"2024-02-19T08:30:14","modified_gmt":"2024-02-19T08:30:14","slug":"linear-search","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/","title":{"rendered":"Linear Search"},"content":{"rendered":"<div class=\"mceTemp\"><\/div>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Linear Search<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Linear Search<\/h3>\n<p>Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.<\/p>\n<p><strong>Algorithm Steps<\/strong><\/p>\n<ol>\n<li>Start at the beginning of the list.<\/li>\n<li>Compare the target value with the current element.<\/li>\n<li>If the target value matches the current element, the search is successful and the position of the element is returned.<\/li>\n<li>If the target value does not match the current element, move to the next element in the list.<\/li>\n<li>Repeat steps 2-4 until a match is found or the end of the list is reached.<\/li>\n<\/ol>\n\n<\/div><h2 class=\"tabtitle\">Demonstration<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Interactive linear Search Demonstration<\/h3>\n<p><iframe loading=\"lazy\" title=\"Linear Search\" src=\"https:\/\/revise.learnlearn.uk\/teachassist\/static\/static_pages\/linear_search.html\" width=\"800\" height=\"400\" frameborder=\"0\"><\/iframe><\/p>\n\n<\/div><h2 class=\"tabtitle\">Complexity<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Time complexity &#8211; O(n)<\/h3>\n<p>Because linear search potentially needs to check each item (n) in the list once in the list, the time complexity is O(n)<\/p>\n<h3>Space complexity O(1)<\/h3>\n<p>The space complexity of a linear search algorithm is generally O(1), which means it uses a constant amount of additional memory regardless of the size of the input data. This is because a linear search does not require any additional data structures or memory allocation that scales with the size of the input.<\/p>\n<p>You may use a few variables for control and temporary storage, but the memory usage remains constant and doesn&#8217;t depend on the size of the input data.<\/p>\n\n<\/div><h2 class=\"tabtitle\">Pros &amp; Cons<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Advantages &amp; Disadvantages of Linear Search<\/h3>\n<p><strong>Advantages<\/strong><\/p>\n<ul>\n<li>Simple and easy to understand<\/li>\n<li>Works on both sorted and unsorted lists<\/li>\n<li>Works well for small data sets<\/li>\n<li>Useful if you expect the item to be near the beginning of the list<\/li>\n<\/ul>\n<p><strong>Disadvantages<\/strong><\/p>\n<ul>\n<li>Inefficient for large data sets<\/li>\n<li>Time complexity: O(n), where n is the size of the list<\/li>\n<li>Can be slow compared to other search algorithms<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Python Code<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Example Python Code Implementation of Linear Search<\/h3>\n<p><iframe loading=\"lazy\" src=\"https:\/\/trinket.io\/embed\/python\/6e4c6ca1f0?start=result\" width=\"100%\" height=\"600\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" allowfullscreen=\"allowfullscreen\" data-mce-fragment=\"1\"><\/iframe><\/p>\n<p><em>How does my implementation above differ to standard Python in the way it handles linear search?<\/em><\/p>\n\n<\/div><h2 class=\"tabtitle\">Challenges<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Programming Challenges<\/h3>\n<p><strong>Challenge 1 &#8211; find the highest <\/strong><\/p>\n<p>Write a function <em>find_highest(list)<\/em> that that takes a list and returns the index of the highest value in the list. If the list is empty, return -1<\/p>\n<p><strong>Challenge 2 &#8211; find an item<\/strong><\/p>\n<p>Write a function <em>find(list, target)<\/em> that takes a list and a target value as an input value and returns the index of the first occurrence of the target.<\/p>\n<p>If the target isn&#8217;t found, return -1<\/p>\n<p><strong>Challenge 3 &#8211; find all items<\/strong><\/p>\n<p>Write a function <em>find_all(list, target)<\/em> that that takes a list and a target value as an input value and returns a list of indexes of all the occurrences of the target value.<\/p>\n<p><strong>Challenge 4 &#8211; find all higher<\/strong><\/p>\n<p>Write a function <em>find_all_higher(list, target)<\/em> that that takes a list and a target value as an input value and returns a list of the values of all items that are higher than the search item<\/p>\n<p><strong>Challenge 5 &#8211; find between<\/strong><\/p>\n<p>Write a function <em>find_all_between(list, lower, upper)<\/em> that that takes a list, a lower value bound and an upper value bound as input values and returns a list of the values of all items that are exclusively between the two values.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Linear Search Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed. Algorithm Steps Start at the beginning of the list. Compare the target value with the current element. If the target&hellip;&nbsp;<a href=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\" class=\"\" rel=\"bookmark\">Read More &raquo;<span class=\"screen-reader-text\">Linear Search<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"off","neve_meta_content_width":100,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.6 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Linear Search - Edexcel iGCSE Computer Science<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Linear Search - Edexcel iGCSE Computer Science\" \/>\n<meta property=\"og:description\" content=\"Linear Search Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed. Algorithm Steps Start at the beginning of the list. Compare the target value with the current element. If the target&hellip;&nbsp;Read More &raquo;Linear Search\" \/>\n<meta property=\"og:url\" content=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\" \/>\n<meta property=\"og:site_name\" content=\"Edexcel iGCSE Computer Science\" \/>\n<meta property=\"article:modified_time\" content=\"2024-02-19T08:30:14+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\",\"url\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\",\"name\":\"Linear Search - Edexcel iGCSE Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website\"},\"datePublished\":\"2023-06-11T20:12:03+00:00\",\"dateModified\":\"2024-02-19T08:30:14+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linear Search\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website\",\"url\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/\",\"name\":\"Edexcel iGCSE Computer Science\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-GB\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Linear Search - Edexcel iGCSE Computer Science","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/","og_locale":"en_GB","og_type":"article","og_title":"Linear Search - Edexcel iGCSE Computer Science","og_description":"Linear Search Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed. Algorithm Steps Start at the beginning of the list. Compare the target value with the current element. If the target&hellip;&nbsp;Read More &raquo;Linear Search","og_url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/","og_site_name":"Edexcel iGCSE Computer Science","article_modified_time":"2024-02-19T08:30:14+00:00","twitter_card":"summary_large_image","twitter_misc":{"Estimated reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/","url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/","name":"Linear Search - Edexcel iGCSE Computer Science","isPartOf":{"@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website"},"datePublished":"2023-06-11T20:12:03+00:00","dateModified":"2024-02-19T08:30:14+00:00","breadcrumb":{"@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/linear-search\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/"},{"@type":"ListItem","position":2,"name":"Linear Search"}]},{"@type":"WebSite","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website","url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/","name":"Edexcel iGCSE Computer Science","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-GB"}]}},"rttpg_featured_image_url":null,"rttpg_author":{"display_name":"learnlearnadmin","author_link":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/author\/learnlearnadmin\/"},"rttpg_comment":0,"rttpg_category":null,"rttpg_excerpt":"Linear Search Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed. Algorithm Steps Start at the beginning of the list. Compare the target value with the current element. If the target&hellip;&nbsp;Read&hellip;","_links":{"self":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/150"}],"collection":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/comments?post=150"}],"version-history":[{"count":6,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/150\/revisions"}],"predecessor-version":[{"id":716,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/150\/revisions\/716"}],"wp:attachment":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/media?parent=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}