{"id":8143,"date":"2025-07-22T10:56:37","date_gmt":"2025-07-22T05:26:37","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=8143"},"modified":"2025-07-22T21:26:31","modified_gmt":"2025-07-22T15:56:31","slug":"find-first-last-position-in-sorted-array-approach-2","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/find-first-last-position-in-sorted-array-approach-2\/","title":{"rendered":"Find First &amp; Last Position in Sorted Array &#8211; Approach 2"},"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<div class=\"wp_blog_explanation\">\n  <p>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.<\/p>\n\n  <h2>Steps<\/h2>\n  <ul>\n    <li>Binary search for the **first index** (on match, shift right side)<\/li>\n    <li>Binary search for the **last index** (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>Dry Run<\/h2>\n  <p><strong>Input:<\/strong> <code>[5,7,7,8,8,10]<\/code>, target = <code>8<\/code><\/p>\n  <ol>\n    <li>First binary search finds first index <code>3<\/code><\/li>\n    <li>Second binary search finds last index <code>4<\/code><\/li>\n    <li>Output: <code>[3, 4]<\/code><\/li>\n  <\/ol>\n\n  <p><strong>Input:<\/strong> target = <code>6<\/code> \u2192 Output: <code>[-1, -1]<\/code><\/p>\n  <p><strong>Input:<\/strong> target = <code>0<\/code> \u2192 Output: <code>[-1, -1]<\/code><\/p>\n\n  <h2>Time &#038; Space Complexity<\/h2>\n  <ul>\n    <li><strong>Time:<\/strong> O(log\u202fn)<\/li>\n    <li><strong>Space:<\/strong> O(1)<\/li>\n  <\/ul>\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    <button class=\"wp_blog_code-tab-button\" data-lang=\"c#\">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\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\n    l = 0;\n    r = arr.length - 1;\n\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\n    return ans;\n};\n    <\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n    <pre><code class=\"language-cpp\">\nvector<int> searchRange(vector<int>& arr, int target) {\n    int l = 0, r = arr.size() - 1;\n    vector<int> ans = {-1, -1};\n\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\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\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\">\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\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\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\n    return ans;\n}\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\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\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\n        return ans;\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\">\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=\"c#\">\n    <pre><code class=\"language-c#\">\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\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\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\n        return ans;\n    }\n}\n    <\/code><\/pre>\n  <\/div>\n<\/div>\n\n\n\n<a href=\"https:\/\/leetcode.com\/problems\/two-sum\/description\/\" target=\"blank\">Solve this problem.<\/a>\n<script>\n  document.addEventListener(\"DOMContentLoaded\", function () {\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        button.classList.add(\"active\");\n\n        contents.forEach((content) => {\n          content.classList.toggle(\"active\", content.getAttribute(\"data-lang\") === lang);\n        });\n      });\n    });\n  });\n<\/script>\n\n\n","protected":false},"excerpt":{"rendered":"<p>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. Steps Binary search for the **first index** (on match, shift right side) Binary search for the **last index** (on match, shift left side)<\/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":[322,176,175,211,174,172,173],"tags":[],"class_list":{"0":"post-8143","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms-and-data-structures","7":"category-csharp","8":"category-cplusplus","9":"category-data-structures","10":"category-java","11":"category-javascript","12":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8143","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=8143"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8143\/revisions"}],"predecessor-version":[{"id":8144,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8143\/revisions\/8144"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=8143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=8143"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=8143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}