{"id":483,"date":"2025-07-02T18:25:02","date_gmt":"2025-07-02T12:55:02","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=483"},"modified":"2025-07-02T18:25:04","modified_gmt":"2025-07-02T12:55:04","slug":"binary-search-leetcode-704","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/","title":{"rendered":"Binary Search | Leetcode 704 | Explained in Python"},"content":{"rendered":"\n<p>Given an array of integers&nbsp;<code>nums<\/code>&nbsp;which is sorted in ascending order, and an integer&nbsp;<code>target<\/code>, write a function to search&nbsp;<code>target<\/code>&nbsp;in&nbsp;<code>nums<\/code>. If&nbsp;<code>target<\/code>&nbsp;exists, then return its index. Otherwise, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>You must write an algorithm with&nbsp;<code>O(log n)<\/code>&nbsp;runtime complexity.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/binary-search\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> nums = [-1,0,3,5,9,12], target = 9<br><strong>Output:<\/strong> 4<br><strong>Explanation:<\/strong> 9 exists in nums and its index is 4<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> nums = [-1,0,3,5,9,12], target = 2<br><strong>Output:<\/strong> -1<br><strong>Explanation:<\/strong> 2 does not exist in nums so return -1<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= nums.length &lt;= 10<sup>4<\/sup><\/code><\/li>\n\n\n\n<li><code>-10<sup>4<\/sup> &lt; nums[i], target &lt; 10<sup>4<\/sup><\/code><\/li>\n\n\n\n<li>All the integers in&nbsp;<code>nums<\/code>&nbsp;are&nbsp;<strong>unique<\/strong>.<\/li>\n\n\n\n<li><code>nums<\/code>&nbsp;is sorted in ascending order.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-c614618b-4109-4e30-8a2a-08a79b8afaa5\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"false\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#0-optimal-solution-\" style=\"\">OPTIMAL SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#1-1-intuition-amp-approach-breaking-it-down-step-by-step-\" style=\"\">1. Intuition &amp; Approach (Breaking it Down Step-by-Step)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#2-understanding-the-problem-\" style=\"\">Understanding the Problem<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#3-why-binary-search-\" style=\"\">Why Binary Search?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#4-how-binary-search-works-\" style=\"\">How Binary Search Works<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#5-2-code-implementation-\" style=\"\">2. Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#6-3-code-explanation-high-level-overview-\" style=\"\">3. Code Explanation (High-Level Overview)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#7-step-1-initialize-search-range-\" style=\"\">Step 1: Initialize Search Range<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#8-step-2-loop-until-low-exceeds-high-\" style=\"\">Step 2: Loop Until low Exceeds high<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#9-step-3-compute-the-middle-index-\" style=\"\">Step 3: Compute the Middle Index<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#10-step-4-compare-numsmid-with-target-\" style=\"\">Step 4: Compare nums[mid] with target<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#11-step-5-return-1-if-target-is-not-found-\" style=\"\">Step 5: Return -1 if Target is Not Found<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#12-4-dry-run-step-by-step-execution-\" style=\"\">4. Dry Run (Step-by-Step Execution)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#13-example-1-\" style=\"\">Example 1<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#14-execution-process-\" style=\"\">Execution Process<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#15-final-output-\" style=\"\">Final Output:<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#16-example-2-target-not-found-\" style=\"\">Example 2 (Target Not Found)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#17-final-output-\" style=\"\">Final Output:<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#18-5-time-and-space-complexity-analysis-\" style=\"\">5. Time and Space Complexity Analysis<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#19-time-complexity-\" style=\"\">Time Complexity:<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#20-space-complexity-\" style=\"\">Space Complexity:<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#21-6-edge-cases-to-consider-\" style=\"\">6. Edge Cases to Consider<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#22-1-target-is-the-first-or-last-element-\" style=\"\">1. Target is the First or Last Element<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#23-2-target-is-not-in-the-array-\" style=\"\">2. Target is Not in the Array<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#24-3-empty-array-\" style=\"\">3. Empty Array<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#25-4-array-contains-one-element-\" style=\"\">4. Array Contains One Element<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#26-5-large-input-case-\" style=\"\">5. Large Input Case<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/binary-search-leetcode-704\/#27-conclusion-\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-optimal-solution-\"><strong>OPTIMAL SOLUTION<\/strong><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-1-intuition-amp-approach-breaking-it-down-step-by-step-\"><strong>1. Intuition &amp; Approach (Breaking it Down Step-by-Step)<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"2-understanding-the-problem-\"><strong>Understanding the Problem<\/strong><\/h4>\n\n\n\n<p>We are given a sorted array (nums) and a target integer (target). Our goal is to determine the index of target in nums. If target is not found, we return -1.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"3-why-binary-search-\"><strong>Why Binary Search?<\/strong><\/h4>\n\n\n\n<p>Instead of checking each element one by one (O(N) time complexity) like linear search, we can leverage the fact that the array is sorted and efficiently reduce our search space by half in each step.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"4-how-binary-search-works-\"><strong>How Binary Search Works<\/strong><\/h4>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Set two pointers (low and high) at the beginning (0) and end (n-1) of the array.<\/li>\n\n\n\n<li>Find the middle index (mid) of the current search range.<\/li>\n\n\n\n<li>Compare nums[mid] with target:\n<ul class=\"wp-block-list\">\n<li>If nums[mid] == target, we return mid (found the target).<\/li>\n\n\n\n<li>If nums[mid] &lt; target, it means target must be on the right half, so we move low = mid + 1.<\/li>\n\n\n\n<li>If nums[mid] &gt; target, it means target must be on the left half, so we move high = mid &#8211; 1.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Repeat the process until low &gt; high (which means target is not present in the array).<\/li>\n<\/ol>\n\n\n\n<p>This approach eliminates half of the remaining elements at each step, making it extremely fast compared to scanning the array linearly.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-2-code-implementation-\"><strong>2. Code Implementation<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def search(self, nums: List[int], target: int) -&gt; int:\n        n = len(nums)\n        low = 0\n        high = n - 1\n\n        while low &lt;= high:\n            mid = (low + high) \/\/ 2  # Find the middle index\n\n            if nums[mid] == target:\n                return mid  # Target found, return index\n\n            elif nums[mid] &lt; target:\n                low = mid + 1  # Move to the right half\n\n            else:\n                high = mid - 1  # Move to the left half\n\n        return -1  # Target not found\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">search<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        low = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        high = n - <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> low &lt;= high:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            mid = (low + high) \/\/ <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Find the middle index<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> nums[mid] == target:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> mid  <\/span><span style=\"color: #6A9955\"># Target found, return index<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> nums[mid] &lt; target:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                low = mid + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Move to the right half<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                high = mid - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Move to the left half<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Target not found<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-3-code-explanation-high-level-overview-\"><strong>3. Code Explanation (High-Level Overview)<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"7-step-1-initialize-search-range-\"><strong>Step 1: Initialize Search Range<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We define low = 0 (start) and high = n &#8211; 1 (end) to keep track of our search space.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"8-step-2-loop-until-low-exceeds-high-\"><strong>Step 2: Loop Until <\/strong><strong>low<\/strong><strong> Exceeds <\/strong><strong>high<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The loop runs until low &lt;= high, ensuring we continue searching as long as there is a valid range.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"9-step-3-compute-the-middle-index-\"><strong>Step 3: Compute the Middle Index<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The middle index is calculated using: mid = (low+high) \/ 2<\/li>\n\n\n\n<li>This splits the array in half at each step.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"10-step-4-compare-numsmid-with-target-\"><strong>Step 4: Compare <\/strong><strong>nums[mid]<\/strong><strong> with <\/strong><strong>target<\/strong><\/h4>\n\n\n\n<ol class=\"wp-block-list\">\n<li>If nums[mid] == target, we return mid (target found).<\/li>\n\n\n\n<li>If nums[mid] &lt; target, move to the right half (low = mid + 1).<\/li>\n\n\n\n<li>If nums[mid] &gt; target, move to the left half (high = mid &#8211; 1).<\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"11-step-5-return-1-if-target-is-not-found-\"><strong>Step 5: Return <\/strong><strong>-1<\/strong><strong> if Target is Not Found<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If the loop exits without finding the target, we return -1 (indicating absence in the array).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-4-dry-run-step-by-step-execution-\"><strong>4. Dry Run (Step-by-Step Execution)<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"13-example-1-\"><strong>Example 1<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>-1<\/strong><strong>, <\/strong><strong>0<\/strong><strong>, <\/strong><strong>3<\/strong><strong>, <\/strong><strong>5<\/strong><strong>, <\/strong><strong>9<\/strong><strong>, <\/strong><strong>12<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>9<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"14-execution-process-\"><strong>Execution Process<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>Step<\/strong><\/td><td><strong>low<\/strong><\/td><td><strong>high<\/strong><\/td><td><strong>mid<\/strong><\/td><td><strong>nums[mid]<\/strong><\/td><td><strong>Action<\/strong><\/td><\/tr><tr><td><strong>1<\/strong><\/td><td><strong>0<\/strong><\/td><td><strong>5<\/strong><\/td><td><strong>2<\/strong><\/td><td><strong>3<\/strong><\/td><td><strong>3 &lt; 9<\/strong><strong>, move right (<\/strong><strong>low = 3<\/strong><strong>)<\/strong><\/td><\/tr><tr><td><strong>2<\/strong><\/td><td><strong>3<\/strong><\/td><td><strong>5<\/strong><\/td><td><strong>4<\/strong><\/td><td><strong>9<\/strong><\/td><td><strong>\u2705 Target found, return <\/strong><strong>4<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"15-final-output-\"><strong>Final Output:<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>4<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"16-example-2-target-not-found-\"><strong>Example 2 (Target Not Found)<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>-1<\/strong><strong>, <\/strong><strong>0<\/strong><strong>, <\/strong><strong>3<\/strong><strong>, <\/strong><strong>5<\/strong><strong>, <\/strong><strong>9<\/strong><strong>, <\/strong><strong>12<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>2<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>Step<\/strong><\/td><td><strong>low<\/strong><\/td><td><strong>high<\/strong><\/td><td><strong>mid<\/strong><\/td><td><strong>nums[mid]<\/strong><\/td><td><strong>Action<\/strong><\/td><\/tr><tr><td><strong>1<\/strong><\/td><td><strong>0<\/strong><\/td><td><strong>5<\/strong><\/td><td><strong>2<\/strong><\/td><td><strong>3<\/strong><\/td><td><strong>3 &gt; 2<\/strong><strong>, move left (<\/strong><strong>high = 1<\/strong><strong>)<\/strong><\/td><\/tr><tr><td><strong>2<\/strong><\/td><td><strong>0<\/strong><\/td><td><strong>1<\/strong><\/td><td><strong>0<\/strong><\/td><td><strong>-1<\/strong><\/td><td><strong>-1 &lt; 2<\/strong><strong>, move right (<\/strong><strong>low = 1<\/strong><strong>)<\/strong><\/td><\/tr><tr><td><strong>3<\/strong><\/td><td><strong>1<\/strong><\/td><td><strong>1<\/strong><\/td><td><strong>1<\/strong><\/td><td><strong>0<\/strong><\/td><td><strong>0 &lt; 2<\/strong><strong>, move right (<\/strong><strong>low = 2<\/strong><strong>)<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Since <\/strong><strong>low (2) &gt; high (1)<\/strong><strong>, loop terminates and returns <\/strong><strong>-1<\/strong><strong> (target not found).<\/strong><\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"17-final-output-\"><strong>Final Output:<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>-1<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-5-time-and-space-complexity-analysis-\"><strong>5. Time and Space Complexity Analysis<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"19-time-complexity-\"><strong>Time Complexity:<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>At each step, we divide the search space in half.<\/li>\n\n\n\n<li>The maximum number of steps required to find an element in an array of size N is log\u2082(N).<\/li>\n\n\n\n<li>Time complexity: O(log\u2061N)<\/li>\n\n\n\n<li>This is significantly faster than a linear search (O(N)).<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"20-space-complexity-\"><strong>Space Complexity:<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The algorithm only uses a few integer variables (low, high, mid).<\/li>\n\n\n\n<li>No extra memory is used, so space complexity is: O(1)<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"21-6-edge-cases-to-consider-\"><strong>6. Edge Cases to Consider<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"22-1-target-is-the-first-or-last-element-\"><strong>1. Target is the First or Last Element<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>1<\/strong><strong>, <\/strong><strong>2<\/strong><strong>, <\/strong><strong>3<\/strong><strong>, <\/strong><strong>4<\/strong><strong>, <\/strong><strong>5<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>1<\/strong><strong>&nbsp; <\/strong><strong># First element<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Expected Output: <\/strong><strong>0<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>1<\/strong><strong>, <\/strong><strong>2<\/strong><strong>, <\/strong><strong>3<\/strong><strong>, <\/strong><strong>4<\/strong><strong>, <\/strong><strong>5<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>5<\/strong><strong>&nbsp; <\/strong><strong># Last element<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Expected Output: <\/strong><strong>4<\/strong><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"23-2-target-is-not-in-the-array-\"><strong>2. Target is Not in the Array<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>2<\/strong><strong>, <\/strong><strong>4<\/strong><strong>, <\/strong><strong>6<\/strong><strong>, <\/strong><strong>8<\/strong><strong>, <\/strong><strong>10<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>5<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Expected Output: <\/strong><strong>-1<\/strong><strong> (not found)<\/strong><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"24-3-empty-array-\"><strong>3. Empty Array<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = []<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>3<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Expected Output: <\/strong><strong>-1<\/strong><strong> (no elements to search)<\/strong><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"25-4-array-contains-one-element-\"><strong>4. Array Contains One Element<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = [<\/strong><strong>7<\/strong><strong>]<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>7<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Expected Output: <\/strong><strong>0<\/strong><strong> (found at index 0)<\/strong><\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"26-5-large-input-case-\"><strong>5. Large Input Case<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>nums = list(range(<\/strong><strong>1<\/strong><strong>, <\/strong><strong>1000001<\/strong><strong>))&nbsp; <\/strong><strong># 1 to 1,000,000<\/strong><strong><br><\/strong><strong>target = <\/strong><strong>999999<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Binary search finds it in log\u2082(10\u2076) \u2248 20 comparisons instead of 1,000,000 comparisons in linear search.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"27-conclusion-\"><strong>Conclusion<\/strong><\/h3>\n\n\n\n<p><strong>\u2705 Why This Solution is Optimal?<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>O(log N) complexity makes it highly efficient for large datasets.<\/li>\n\n\n\n<li>O(1) space complexity (no extra storage required).<\/li>\n\n\n\n<li>Works for any sorted array, regardless of size.<\/li>\n\n\n\n<li>Much faster than linear search, especially for large inputs.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of integers&nbsp;nums&nbsp;which is sorted in ascending order, and an integer&nbsp;target, write a function to search&nbsp;target&nbsp;in&nbsp;nums. If&nbsp;target&nbsp;exists, then return its index. Otherwise, return&nbsp;-1. You must write an algorithm with&nbsp;O(log n)&nbsp;runtime complexity. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9Output: 4Explanation: 9 exists in nums and<\/p>\n","protected":false},"author":1,"featured_media":487,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,4],"tags":[7,27],"class_list":{"0":"post-483","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-array","10":"tag-binary-search"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/binary-search-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/483","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=483"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/483\/revisions"}],"predecessor-version":[{"id":491,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/483\/revisions\/491"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/487"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=483"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=483"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=483"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}