{"id":6173,"date":"2025-05-29T18:48:11","date_gmt":"2025-05-29T13:18:11","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=6173"},"modified":"2025-05-29T18:48:11","modified_gmt":"2025-05-29T13:18:11","slug":"binary-search","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/binary-search\/","title":{"rendered":"Binary Search"},"content":{"rendered":"\n<!-- Prism.js CSS and JS -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.css\" rel=\"stylesheet\" \/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_code-tabs-container {\n    font-family: \"Segoe UI\", sans-serif !important;\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    border: 1px solid #ddd !important;\n    border-radius: 8px !important;\n    overflow: hidden !important;\n    background-color: white !important;\n}\n\n.wp_blog_code-tabs-header {\n    background: #f7f7f7 !important;\n    display: flex !important;\n    border-bottom: 1px solid #ddd !important;\n}\n\n.wp_blog_code-tab-button {\n    flex: 1 !important;\n    padding: 10px 15px !important;\n    border: none !important;\n    background: transparent !important;\n    cursor: pointer !important;\n    font-weight: bold !important;\n    transition: background 0.2s !important;\n    color: #242B33 !important;\n}\n\n.wp_blog_code-tab-button.active {\n    background: white !important;\n    border-bottom: 3px solid #0073aa !important;\n}\n\n.wp_blog_code-tab-content {\n    display: none !important;\n    padding: 20px !important;\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content > pre {\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content.active {\n    display: block !important;\n}\n\n.wp_blog_code-tab-content pre {\n    margin: 0 !important;\n    overflow-x: auto !important;\n}\n\n.wp_blog_explanation {\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    font-family: \"Segoe UI\", sans-serif !important;\n    line-height: 1.6 !important;\n    background: white !important;\n    color: black !important;\n    padding: 1rem !important;\n    border-radius: 8px !important;\n}\n\n.wp_blog_explanation h2 {\n    color: #0073aa !important;\n    font-size: 1.5rem !important;\n    margin-bottom: 0.5rem !important;\n}\n\n.wp_blog_explanation code {\n    background: #f1f1f1 !important;\n    padding: 2px 6px !important;\n    border-radius: 4px !important;\n    font-family: monospace !important;\n}\n\n.wp_blog_explanation h1,\n.wp_blog_explanation h2,\n.wp_blog_explanation h3,\n.wp_blog_explanation h4,\n.wp_blog_explanation h5,\n.wp_blog_explanation h6,\n.wp_blog_explanation p {\n    margin-top: 10px !important;\n    margin-bottom: 10px !important;\n}\n<\/style>\n\n<!-- \u2705 START: Blog Explanation -->\n\n<div class=\"wp_blog_explanation\">\n<p>\n  Binary Search is an efficient algorithm used to find the position of a target value within a <strong>sorted array<\/strong>.\n  Unlike linear search, it repeatedly divides the search interval in half, significantly reducing the number of comparisons.\n<\/p>\n\n<h2>Approach<\/h2>\n<ol>\n  <li>Set <code>left = 0<\/code>, <code>right = nums.length - 1<\/code>.<\/li>\n  <li>While <code>left &lt;= right<\/code>:<\/li>\n  <ul>\n    <li>Calculate <code>middle = Math.floor((left + right) \/ 2)<\/code>.<\/li>\n    <li>If <code>nums[middle] === target<\/code>, return <code>middle<\/code>.<\/li>\n    <li>If <code>target &lt; nums[middle]<\/code>, discard the right half: <code>right = middle - 1<\/code>.<\/li>\n    <li>Else, discard the left half: <code>left = middle + 1<\/code>.<\/li>\n  <\/ul>\n  <li>If the target is not found, return <code>-1<\/code>.<\/li>\n<\/ol>\n\n<h2>Example:<\/h2>\n<p>\n  Given array: <code>[1, 3, 5, 7, 9]<\/code><br>\n  Target: <code>7<\/code>\n<\/p>\n\n<h2>Dry Run:<\/h2>\n<pre>\nInitial: left = 0, right = 4\nmiddle = Math.floor((0 + 4) \/ 2) = 2 \u2192 nums[2] = 5\n\u2192 target > 5 \u2192 update left = 3\n\nNext: middle = Math.floor((3 + 4) \/ 2) = 3 \u2192 nums[3] = 7\n\u2192 target found \u2192 return 3\n<\/pre>\n\n<h2>Time Complexity:<\/h2>\n<ul>\n  <li><strong>Best Case:<\/strong> O(1) \u2013 when the target is found at the middle initially<\/li>\n  <li><strong>Worst Case:<\/strong> O(log n) \u2013 the array is halved every iteration<\/li>\n<\/ul>\n\n<h2>Space Complexity:<\/h2>\n<ul>\n  <li><strong>O(1)<\/strong> \u2013 constant space is used (no additional data structures)<\/li>\n<\/ul>\n\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n      <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\n  var search = function(nums, target) {\n    let left = 0;\n    let right = nums.length - 1;\n  \n    while (right >= left) {\n      let middle = Math.floor((left + right) \/ 2);\n  \n      if (target === nums[middle]) {\n        return middle;\n      } else if (target < nums[middle]) {\n        right = middle - 1;\n      } else {\n        left = middle + 1;\n      }\n    }\n  \n    return -1;\n  };\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n  class Solution {\n  public:\n    int search(vector&lt;int&gt;& nums, int target) {\n      int left = 0;\n      int right = nums.size() - 1;\n  \n      while (left <= right) {\n        int middle = left + (right - left) \/ 2;\n  \n        if (nums[middle] == target) {\n          return middle;\n        } else if (target < nums[middle]) {\n          right = middle - 1;\n        } else {\n          left = middle + 1;\n        }\n      }\n  \n      return -1;\n    }\n  };\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n  int search(int* nums, int numsSize, int target) {\n    int left = 0;\n    int right = numsSize - 1;\n  \n    while (left <= right) {\n      int middle = left + (right - left) \/ 2;\n  \n      if (nums[middle] == target) {\n        return middle;\n      } else if (target < nums[middle]) {\n        right = middle - 1;\n      } else {\n        left = middle + 1;\n      }\n    }\n  \n    return -1; \/\/ Target not found\n  }\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\n  public class Solution {\n    public static int search(int[] nums, int target) {\n      int left = 0, right = nums.length - 1;\n  \n      while (left <= right) {\n        int middle = left + (right - left) \/ 2;\n  \n        if (nums[middle] == target) {\n          return middle;\n        } else if (target < nums[middle]) {\n          right = middle - 1;\n        } else {\n          left = middle + 1;\n        }\n      }\n  \n      return -1;\n    }\n  }\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\n  class Solution(object):\n    def search(self, nums, target):\n      \"\"\"\n      :type nums: List[int]\n      :type target: int\n      :rtype: int\n      \"\"\"\n      left = 0\n      right = len(nums) - 1\n  \n      while left <= right:\n        middle = (left + right) \/\/ 2\n  \n        if nums[middle] == target:\n          return middle\n        elif target < nums[middle]:\n          right = middle - 1\n        else:\n          left = middle + 1\n  \n      return -1  # Target not found\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n  \n  \n  \n<!-- \u2705 JS Tab Switch Logic -->\n<script>\ndocument.addEventListener('DOMContentLoaded', function () {\n    const buttons = document.querySelectorAll('.wp_blog_code-tab-button');\n    const contents = document.querySelectorAll('.wp_blog_code-tab-content');\n    buttons.forEach(button => {\n        button.addEventListener('click', () => {\n            const lang = button.getAttribute('data-lang');\n            buttons.forEach(btn => btn.classList.remove('active'));\n            button.classList.add('active');\n            contents.forEach(content => {\n                content.classList.toggle('active', content.getAttribute('data-lang') === lang);\n            });\n        });\n    });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Binary Search is an efficient algorithm used to find the position of a target value within a sorted array. Unlike linear search, it repeatedly divides the search interval in half, significantly reducing the number of comparisons. Approach Set left = 0, right = nums.length &#8211; 1. While left &lt;= right: Calculate middle = Math.floor((left +<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[811,810],"tags":[],"class_list":["post-6173","post","type-post","status-publish","format-standard","category-data-structures-and-algorithms","category-dsa"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6173","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=6173"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6173\/revisions"}],"predecessor-version":[{"id":6174,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6173\/revisions\/6174"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=6173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=6173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=6173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}