{"id":8139,"date":"2025-07-22T10:52:43","date_gmt":"2025-07-22T05:22:43","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=8139"},"modified":"2025-07-22T21:28:09","modified_gmt":"2025-07-22T15:58:09","slug":"find-minimum-in-rotated-sorted-array","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/find-minimum-in-rotated-sorted-array\/","title":{"rendered":"Find Minimum in Rotated Sorted Array"},"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\n<div class=\"wp_blog_explanation\">\n  <p>This problem asks us to find the smallest element in an array that was originally sorted in ascending order and then rotated. The array has no duplicates.<\/p>\n\n  <h2>Steps<\/h2>\n  <ul>\n    <li>We use binary search to locate the minimum element efficiently.<\/li>\n    <li>Initialize <code>l = 0<\/code> and <code>r = a.length - 1<\/code>.<\/li>\n    <li>While <code>l \u2264 r<\/code>:\n      <ul>\n        <li>If <code>a[l] \u2264 a[r]<\/code> \u2192 subarray is sorted \u2192 return <code>a[l]<\/code>.<\/li>\n        <li>Find mid: <code>m = l + floor((r - l) \/ 2)<\/code><\/li>\n        <li>If <code>a[m] &lt; a[m - 1]<\/code> \u2192 pivot found \u2192 return <code>a[m]<\/code><\/li>\n        <li>If <code>a[l] &gt; a[m]<\/code> \u2192 rotation point is left \u2192 <code>r = m - 1<\/code><\/li>\n        <li>Else \u2192 rotation point is right \u2192 <code>l = m + 1<\/code><\/li>\n      <\/ul>\n    <\/li>\n  <\/ul>\n\n  <h2>Dry Run<\/h2>\n  <p><strong>Input:<\/strong> <code>[3,4,5,1,2]<\/code><\/p>\n  <ol>\n    <li>l=0, r=4 \u2192 m=2 \u2192 5 &gt; 1 \u2192 move left \u2192 r=2<\/li>\n    <li>m=1 \u2192 4 &gt; 5 \u2192 l=2<\/li>\n    <li>m=2 \u2192 5 &gt; 1 \u2192 r=1<\/li>\n    <li>m=0 \u2192 3 &lt; 4 \u2192 array sorted \u2192 return 1<\/li>\n  <\/ol>\n  <p><strong>Output:<\/strong> <code>1<\/code><\/p>\n\n  <p><strong>Input:<\/strong> <code>[4,5,6,70,1,2]<\/code><\/p>\n  <p><strong>Output:<\/strong> <code>1<\/code><\/p>\n\n  <h2>Time &#038; Space Complexity<\/h2>\n  <ul>\n    <li><strong>Time Complexity:<\/strong> O(log\u202fn)<\/li>\n    <li><strong>Space Complexity:<\/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 findMin = function(a) {\n    let l = 0;\n    let r = a.length - 1;\n\n    while (l <= r) {\n        if (a[l] <= a[r]) {\n            return a[l];\n        }\n\n        let m = l + Math.floor((r - l) \/ 2);\n        if (a[m] < a[m - 1]) {\n            return a[m];\n        }\n\n        if (a[l] > a[m]) {\n            r = m - 1;\n        } else {\n            l = m + 1;\n        }\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\">\nint findMin(vector<int>& a) {\n    int l = 0, r = a.size() - 1;\n    while (l <= r) {\n        if (a[l] <= a[r]) return a[l];\n\n        int m = l + (r - l) \/ 2;\n        if (a[m] < a[m - 1]) return a[m];\n\n        if (a[l] > a[m]) r = m - 1;\n        else l = m + 1;\n    }\n    return -1;\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 findMin(int* a, int aSize) {\n    int l = 0, r = aSize - 1;\n    while (l <= r) {\n        if (a[l] <= a[r]) return a[l];\n\n        int m = l + (r - l) \/ 2;\n        if (m > 0 && a[m] < a[m - 1]) return a[m];\n\n        if (a[l] > a[m]) r = m - 1;\n        else l = m + 1;\n    }\n    return -1;\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 findMin(int[] a) {\n        int l = 0, r = a.length - 1;\n        while (l <= r) {\n            if (a[l] <= a[r]) return a[l];\n\n            int m = l + (r - l) \/ 2;\n            if (m > 0 && a[m] < a[m - 1]) return a[m];\n\n            if (a[l] > a[m]) r = m - 1;\n            else l = m + 1;\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\">\ndef findMin(a):\n    l, r = 0, len(a) - 1\n    while l <= r:\n        if a[l] <= a[r]:\n            return a[l]\n\n        m = l + (r - l) \/\/ 2\n        if m > 0 and a[m] < a[m - 1]:\n            return a[m]\n\n        if a[l] > a[m]:\n            r = m - 1\n        else:\n            l = m + 1\n    return -1\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 FindMin(int[] a) {\n        int l = 0, r = a.Length - 1;\n        while (l <= r) {\n            if (a[l] <= a[r]) return a[l];\n\n            int m = l + (r - l) \/ 2;\n            if (m > 0 && a[m] < a[m - 1]) return a[m];\n\n            if (a[l] > a[m]) r = m - 1;\n            else l = m + 1;\n        }\n        return -1;\n    }\n}\n    <\/code><\/pre>\n  <\/div>\n<\/div>\n\n\n\n\n<a href=\"https:\/\/leetcode.com\/problems\/find-minimum-in-rotated-sorted-array\/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 problem asks us to find the smallest element in an array that was originally sorted in ascending order and then rotated. The array has no duplicates. Steps We use binary search to locate the minimum element efficiently. Initialize l = 0 and r = a.length &#8211; 1. While l \u2264 r: If a[l] \u2264<\/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":["post-8139","post","type-post","status-publish","format-standard","category-algorithms-and-data-structures","category-csharp","category-cplusplus","category-data-structures","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8139","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=8139"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8139\/revisions"}],"predecessor-version":[{"id":8140,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8139\/revisions\/8140"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=8139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=8139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=8139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}