{"id":10046,"date":"2025-09-09T14:55:32","date_gmt":"2025-09-09T09:25:32","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10046"},"modified":"2025-09-09T15:45:55","modified_gmt":"2025-09-09T10:15:55","slug":"find-first-and-last-position-in-sorted-array-second_approach","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/find-first-and-last-position-in-sorted-array-second_approach\/","title":{"rendered":"Find First and Last Position in Sorted Array Approach 2"},"content":{"rendered":"\n\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\">\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.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_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n       This version <strong>improves clarity by separating<\/strong> the two binary searches more cleanly. We <code>use one binary search<\/code> to find the first index, and another to find the <strong>last index<\/strong> of the target.\n    <\/p> \n\n    <h2>Approach:<\/h2>\n    <ul>\n        <li><code>Binary search<\/code> for the <strong>**first index**<\/strong> (on match, shift right side).<\/li>\n        <li>Binary search for the <strong>**last index**<\/strong> (on match, shift left side).<\/li>\n        <li>Update <code>ans[0]<\/code> and <code>ans[1]<\/code> accordingly.<\/li>\n    <\/ul>\n\n    <h2>Time &#038; Space Complexity:<\/h2>\n    <p><strong>Time Complexity:<\/strong> O(logn)<\/p>\n    <p><strong>Space Complexity:<\/strong> O(1)<\/p>\n\n\n    \n<h2>Dry Run<\/h2>\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\">\n  <p><strong>Input:<\/strong> <code>arr = [5, 7, 7, 8, 8, 10], target = 8<\/code><\/p>\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\n\nInitial:\nl = 0, r = 5\nans = [-1, -1]\n\n--- First While Loop (find first index) ---\n\nLoop 1:\nm = 0 + Math.floor((5 - 0) \/ 2) = 2\narr[m] = 7 < 8 \u2192 true\nl = m + 1 = 3\n\nLoop 2:\nm = 3 + Math.floor((5 - 3) \/ 2) = 4\narr[m] = 8 < 8 \u2192 false\nr = m = 4\n\nLoop 3:\nm = 3 + Math.floor((4 - 3) \/ 2) = 3\narr[m] = 8 < 8 \u2192 false\nr = m = 3\n\nExit (l = 3, r = 3)\narr[l] = 8 \u2192 ans[0] = 3\n\n--- Second While Loop (find last index) ---\n\nReset: l = 0, r = 5\n\nLoop 1:\nm = 0 + Math.ceil((5 - 0) \/ 2) = 3\narr[m] = 8 > 8 \u2192 false\nl = m = 3\n\nLoop 2:\nm = 3 + Math.ceil((5 - 3) \/ 2) = 4\narr[m] = 8 > 8 \u2192 false\nl = m = 4\n\nLoop 3:\nm = 4 + Math.ceil((5 - 4) \/ 2) = 5\narr[m] = 10 > 8 \u2192 true\nr = m - 1 = 4\n\nExit (l = 4, r = 4)\narr[l] = 8 \u2192 ans[1] = 4\n\n--- Final Result ---\nans = [3, 4]\n  <\/pre>\n  <p><strong>Output:<\/strong> <code>Result: [3, 4]<\/code><\/p>\n<\/div>\n\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=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/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=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\nvar searchRange = function(arr, target) {\n    let l = 0;\n    let r = arr.length - 1;\n    let ans = [-1, -1];\n    while (l <= r) {\n        let m = l + Math.floor((r - l) \/ 2);\n        if (arr[m] === target) {\n            ans[0] = m;\n            r = m - 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    l = 0;\n    r = arr.length - 1;\n    while (l <= r) {\n        let m = l + Math.floor((r - l) \/ 2);\n        if (arr[m] === target) {\n            ans[1] = m;\n            l = m + 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    return ans;\n};\n      <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\ndef searchRange(arr, target):\n    ans = [-1, -1]\n    l, r = 0, len(arr) - 1\n\n    while l <= r:\n        m = l + (r - l) \/\/ 2\n        if arr[m] == target:\n            ans[0] = m\n            r = m - 1\n        elif arr[m] < target:\n            l = m + 1\n        else:\n            r = m - 1\n\n    l, r = 0, len(arr) - 1\n    while l <= r:\n        m = l + (r - l) \/\/ 2\n        if arr[m] == target:\n            ans[1] = m\n            l = m + 1\n        elif arr[m] < target:\n            l = m + 1\n        else:\n            r = m - 1\n\n    return ans\n      <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\npublic class Solution {\n    public int[] searchRange(int[] arr, int target) {\n        int[] ans = {-1, -1};\n        int l = 0, r = arr.length - 1;\n        while (l <= r) {\n            int m = l + (r - l) \/ 2;\n            if (arr[m] == target) {\n                ans[0] = m;\n                r = m - 1;\n            } else if (arr[m] < target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        l = 0; r = arr.length - 1;\n        while (l <= r) {\n            int m = l + (r - l) \/ 2;\n            if (arr[m] == target) {\n                ans[1] = m;\n                l = m + 1;\n            } else if (arr[m] < target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        return ans;\n    }\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<!-- #include &lt;iostream&gt; -->\nvector searchRange(vector& arr, int target) {\n    int l = 0, r = arr.size() - 1;\n    vector ans = {-1, -1};\n    while (l <= r) {\n        int m = l + (r - l) \/ 2;\n        if (arr[m] == target) {\n            ans[0] = m;\n            r = m - 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    l = 0; r = arr.size() - 1;\n    while (l <= r) {\n        int m = l + (r - l) \/ 2;\n        if (arr[m] == target) {\n            ans[1] = m;\n            l = m + 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    return ans;\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<!-- #include &lt;stdio.h&gt; -->\nint* searchRange(int* arr, int arrSize, int target, int* returnSize) {\n    int* ans = (int*)malloc(2 * sizeof(int));\n    *returnSize = 2;\n    ans[0] = ans[1] = -1;\n    int l = 0, r = arrSize - 1;\n    while (l <= r) {\n        int m = l + (r - l) \/ 2;\n        if (arr[m] == target) {\n            ans[0] = m;\n            r = m - 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    l = 0; r = arrSize - 1;\n    while (l <= r) {\n        int m = l + (r - l) \/ 2;\n        if (arr[m] == target) {\n            ans[1] = m;\n            l = m + 1;\n        } else if (arr[m] < target) {\n            l = m + 1;\n        } else {\n            r = m - 1;\n        }\n    }\n    return ans;\n}\n      <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n      <pre><code class=\"language-csharp\">\npublic class Solution {\n    public int[] SearchRange(int[] arr, int target) {\n        int[] ans = {-1, -1};\n        int l = 0, r = arr.Length - 1;\n        while (l <= r) {\n            int m = l + (r - l) \/ 2;\n            if (arr[m] == target) {\n                ans[0] = m;\n                r = m - 1;\n            } else if (arr[m] < target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        l = 0; r = arr.Length - 1;\n        while (l <= r) {\n            int m = l + (r - l) \/ 2;\n            if (arr[m] == target) {\n                ans[1] = m;\n                l = m + 1;\n            } else if (arr[m] < target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        return ans;\n    }\n}\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: This version improves clarity by separating the two binary searches more cleanly. We use one binary search to find the first index, and another to find the last index of the target. Approach: Binary search for the **first index** (on match, shift right side). Binary search for the **last index** (on match,<\/p>\n","protected":false},"author":108,"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":[210,322,260,176,175,211,811,810,174,172,173],"tags":[],"class_list":["post-10046","post","type-post","status-publish","format-standard","category-algorithms","category-algorithms-and-data-structures","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10046","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\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10046"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10046\/revisions"}],"predecessor-version":[{"id":10053,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10046\/revisions\/10053"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}