{"id":120330,"date":"2023-11-10T18:00:15","date_gmt":"2023-11-10T12:30:15","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=120330"},"modified":"2023-11-10T19:13:58","modified_gmt":"2023-11-10T13:43:58","slug":"binary-search-in-c","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/","title":{"rendered":"Binary Search in C"},"content":{"rendered":"<p>Searching algorithms play a crucial role in the realm of computer science and programming. They allow us to efficiently find an item from a collection of data. Binary search in C is one such algorithm that makes searching extremely fast and efficient.<\/p>\n<p>Binary search in C uses a divide-and-conquer strategy to significantly speed up searching in sorted data as opposed to linear search, which examines each element one at a time. This article will offer a straightforward explanation of binary search along with C code samples for beginners.<\/p>\n<h2>When to Apply Binary Search in C?<\/h2>\n<p>Binary search in C only works on sorted data sets. The collection must be arranged in ascending or descending order. This sorting enables the divide-and-conquer approach.<\/p>\n<p><strong>C Binary search can be applied to:<\/strong><\/p>\n<ul>\n<li>Sorted arrays<\/li>\n<li>Linked lists<\/li>\n<li>Binary search trees<\/li>\n<\/ul>\n<p>If the data is unsorted, the binary search will fail. Linear search is better suited for unsorted data.<\/p>\n<h3>How Binary Search in C Works<\/h3>\n<p>The binary search in C follows a divide-and-conquer strategy. It continuously divides the search space in half, inspects the middle element, and repeats until the target is found or the search space is exhausted.<\/p>\n<p><strong>The key steps are:<\/strong><\/p>\n<p>1. Find midpoint index of the entire dataset.<br \/>\n2. Compare element at midpoint against target value.<br \/>\n3. If equal, return index of match.<br \/>\n4. If less, repeat search on left half.<br \/>\n5. If greater, repeat search on right half.<\/p>\n<p>This recursive halving of search space enables tremendous efficiency gains.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c-1.webp\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-120752 size-full\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c-1.webp\" alt=\"binary search in c\" width=\"600\" height=\"400\" \/><\/a><\/p>\n<p><strong>Here is a step-by-step example to explain how the binary search algorithm works:<\/strong><\/p>\n<p>Let&#8217;s say we have a sorted array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} and we want to search for the value 23.<\/p>\n<p><strong>The steps are:<\/strong><\/p>\n<ul>\n<li>Set lower index to 0 and the upper index to n-1. Here, n is the number of elements in the array, which is 10. So lower = 0 and upper = 9 (10-1 = 9)<\/li>\n<li>Calculate the mid index as mid = (lower + upper) \/ 2. In this case, mid = (0 + 9) \/ 2 = 4.<\/li>\n<li>Compare the value at arr[mid] with the target value 23. Here arr[mid] is arr[4], which is 16.<\/li>\n<li>Since 16 is less than 23, the target is greater than the mid element. So set lower = mid + 1. This eliminates the left half of the array.<\/li>\n<li>Recalculate mid index with new lower and upper bounds. mid = (lower + upper) \/ 2 = (5 + 9) \/ 2 = 7<\/li>\n<li>Check if arr[mid] (which is 38) equals target. It does not. Since 38 &gt; 23, set upper = mid &#8211; 1. This eliminates the right half.<\/li>\n<li>Recalculate mid as (lower + upper) \/ 2 = (5 + 6) \/ 2 = 5<\/li>\n<li>Check arr[mid] (which is 23) against the target 23. It matches!<\/li>\n<li>Return the index mid.<\/li>\n<\/ul>\n<p>So, in summary, we first compared against the middle element to eliminate half the array, then repeated the process, treating the remaining elements as new arrays until the target was found.<\/p>\n<h3>Binary Search Algorithm in C<\/h3>\n<p><strong>More formally, the binary search algorithm involves:<\/strong><\/p>\n<p>1. Set lowerIndex = 0, upperIndex = size &#8211; 1<br \/>\n2. Compute midpoint index: midIndex = (lowerIndex + upperIndex) \/ 2<br \/>\n3. If array[midIndex] == target, return midIndex<br \/>\n4. Else if array[midIndex] &lt; target, set lowerIndex = midIndex + 1<br \/>\n5. Else set upperIndex = midIndex &#8211; 1<br \/>\n6. Repeat steps 2-5 until target is found or the search space exhausted<\/p>\n<h3>Implementing Binary Search in C<\/h3>\n<p><strong>Binary search can be implemented iteratively or recursively in C:<\/strong><\/p>\n<h4>1) Iterative Implementation<\/h4>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\r\n\r\nint binarySearch(int array[], int n, int target) {\r\n  \r\n  int lowerIndex = 0;\r\n  int upperIndex = n-1;\r\n  \r\n  while(lowerIndex &lt;= upperIndex) {\r\n  \r\n    int midIndex = (lowerIndex + upperIndex) \/ 2;\r\n    \r\n    if(array[midIndex] == target) {\r\n      return midIndex; \r\n    }\r\n    \r\n    if(array[midIndex] &lt; target) {\r\n      lowerIndex = midIndex + 1;\r\n    } \r\n    \r\n    else {\r\n      upperIndex = midIndex - 1;   \r\n    }\r\n    \r\n  }\r\n  \r\n  return -1;\r\n}\r\n\r\nint main() {\r\n\r\n  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};\r\n  \r\n  int n = sizeof(arr)\/sizeof(arr[0]);\r\n  \r\n  int target = 16;\r\n  \r\n  int index = binarySearch(arr, n, target);\r\n  \r\n  if(index != -1) {\r\n    printf(\"Element found at index %d\", index);\r\n  }\r\n  else {\r\n    printf(\"Element not found\");\r\n  }\r\n  \r\n  return 0;\r\n}<\/pre>\n<p><strong>Output:<\/strong><\/p>\n<p>Element found at index 4<\/p>\n<h4>2) Recursive Implementation<\/h4>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\r\n\r\nint binarySearch(int array[], int lowerIndex, int upperIndex, int target) {\r\n\r\n  if (lowerIndex &gt; upperIndex) {\r\n    return -1;\r\n  }\r\n\r\n  int midIndex = (lowerIndex + upperIndex) \/ 2;\r\n\r\n  if (array[midIndex] == target) {\r\n    return midIndex;\r\n  }\r\n\r\n  if (array[midIndex] &lt; target) {\r\n    return binarySearch(array, midIndex + 1, upperIndex, target); \r\n  }\r\n\r\n  return binarySearch(array, lowerIndex, midIndex - 1, target);\r\n\r\n}\r\n\r\nint main() {\r\n  \r\n  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};\r\n  int n = sizeof(arr)\/sizeof(arr[0]);\r\n  \r\n  int target = 16;\r\n  \r\n  int index = binarySearch(arr, 0, n-1, target);\r\n  \r\n  if(index != -1) {\r\n    printf(\"Element found at index %d\", index);\r\n  }\r\n  else {\r\n    printf(\"Element not found\");\r\n  }\r\n\r\n  return 0;\r\n}<\/pre>\n<p><strong>Output:<\/strong><\/p>\n<p>Element found at index 4<\/p>\n<p>The recursive approach is more elegant but can be less efficient due to function call overheads.<\/p>\n<h3>Advantages of Binary Search in C<\/h3>\n<p><strong>Binary search provides:<\/strong><\/p>\n<ul>\n<li>Faster search in sorted data O(log n) vs O(n) for linear search.<\/li>\n<li>Efficient lookup for data stored in arrays, trees, etc.<\/li>\n<li>Better performance than linear search for large data sizes.<\/li>\n<li>Ability to leverage divide-and-conquer algorithms.<\/li>\n<\/ul>\n<h3>Limitations of Binary Search in C<\/h3>\n<p><strong>Some limitations include:<\/strong><\/p>\n<ul>\n<li>Data must be sorted first.<\/li>\n<li>Extra memory is needed for recursive implementation.<\/li>\n<li>Not easily parallelizable due to data dependencies.<\/li>\n<\/ul>\n<h3>Time and Space Complexity Analysis<\/h3>\n<h4>1) Time Complexity<\/h4>\n<table>\n<tbody>\n<tr>\n<td><b>Case<\/b><\/td>\n<td><b>Time Complexity<\/b><\/td>\n<\/tr>\n<tr>\n<td><b>Best Case<\/b><\/td>\n<td><span style=\"font-weight: 400\">O(1)<\/span><\/td>\n<\/tr>\n<tr>\n<td><b>Average Case<\/b><\/td>\n<td><span style=\"font-weight: 400\">O(logn)<\/span><\/td>\n<\/tr>\n<tr>\n<td><b>Worst Case<\/b><\/td>\n<td><span style=\"font-weight: 400\">O(logn)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h4>2) Space Complexity: O(1)<\/h4>\n<h3>Applications of C Binary Search<\/h3>\n<p><strong>C Binary search is used extensively in areas like:<\/strong><\/p>\n<ul>\n<li>Database lookup<\/li>\n<li>Technical documentation search<\/li>\n<li>Data compression<\/li>\n<li>Version control systems<\/li>\n<li>Low level caches<\/li>\n<\/ul>\n<p>It shines when fast lookups are needed in sorted data.<\/p>\n<h3>Common Pitfalls<\/h3>\n<p><strong>Some common mistakes are:<\/strong><\/p>\n<ul>\n<li>Not validating data is sorted first<\/li>\n<li>Subtle off-by-one errors in index computation<\/li>\n<li>Edge case bugs in loop termination conditions<\/li>\n<\/ul>\n<p>Carefully testing edge cases and using debug prints can help identify issues.<\/p>\n<h3>Conclusion<\/h3>\n<p>Binary search in C is an indispensable algorithm for many programming applications. Its divide-and-conquer approach provides logarithmic time lookups in sorted data. While simple in principle, care is needed in implementation to avoid edge case bugs. Overall, binary search in C should be in every coder&#8217;s toolkit for writing performant search functionality.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Searching algorithms play a crucial role in the realm of computer science and programming. They allow us to efficiently find an item from a collection of data. Binary search in C is one such&#46;&#46;&#46;<\/p>\n","protected":false},"author":581,"featured_media":120332,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19488],"tags":[28351,28352,28353,23914],"class_list":["post-120330","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-programming","tag-binary-search-in-c","tag-c-binary-search","tag-c-program-for-binary-search","tag-c-programming"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Binary Search in C - DataFlair<\/title>\n<meta name=\"description\" content=\"Binary search in C is an indispensable algorithm. Its divide-and-conquer approach provides logarithmic time lookups in sorted data.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Binary Search in C - DataFlair\" \/>\n<meta property=\"og:description\" content=\"Binary search in C is an indispensable algorithm. Its divide-and-conquer approach provides logarithmic time lookups in sorted data.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-11-10T12:30:15+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-10T13:43:58+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Binary Search in C - DataFlair","description":"Binary search in C is an indispensable algorithm. Its divide-and-conquer approach provides logarithmic time lookups in sorted data.","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:\/\/data-flair.training\/blogs\/binary-search-in-c\/","og_locale":"en_US","og_type":"article","og_title":"Binary Search in C - DataFlair","og_description":"Binary search in C is an indispensable algorithm. Its divide-and-conquer approach provides logarithmic time lookups in sorted data.","og_url":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2023-11-10T12:30:15+00:00","article_modified_time":"2023-11-10T13:43:58+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp","type":"image\/webp"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/c187795dc82ab948373cca526df7c445"},"headline":"Binary Search in C","datePublished":"2023-11-10T12:30:15+00:00","dateModified":"2023-11-10T13:43:58+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/"},"wordCount":768,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp","keywords":["binary search in c","c binary search","c program for binary search","c programming"],"articleSection":["C Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/","url":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/","name":"Binary Search in C - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp","datePublished":"2023-11-10T12:30:15+00:00","dateModified":"2023-11-10T13:43:58+00:00","description":"Binary search in C is an indispensable algorithm. Its divide-and-conquer approach provides logarithmic time lookups in sorted data.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/binary-search-in-c\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/09\/binary-search-in-c.webp","width":1200,"height":628,"caption":"binary search in c"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/binary-search-in-c\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"C Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/c-programming\/"},{"@type":"ListItem","position":3,"name":"Binary Search in C"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/c187795dc82ab948373cca526df7c445","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/2302ebc438084d2f1f993edc1996a0aae01332e81f3227cba8df0c48ec010ca4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/2302ebc438084d2f1f993edc1996a0aae01332e81f3227cba8df0c48ec010ca4?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/2302ebc438084d2f1f993edc1996a0aae01332e81f3227cba8df0c48ec010ca4?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team provides high-impact content on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. We make complex concepts easy to grasp, helping learners of all levels succeed in their tech careers.","url":"https:\/\/data-flair.training\/blogs\/author\/dfteam6\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/120330","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/581"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=120330"}],"version-history":[{"count":5,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/120330\/revisions"}],"predecessor-version":[{"id":125747,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/120330\/revisions\/125747"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/120332"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=120330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=120330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=120330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}