Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Binary Search

EASYProblemSolveExternal Links

Description

You are given a sorted array of integers arr[] and an integer k. Your task is to find the position (0-based index) at which k is present in the array using the Binary Search algorithm.

If k does not exist in the array, return -1.

Important: If k appears multiple times in the array, return the smallest (leftmost) index where it occurs.

Examples

Example 1

Input: arr = [1, 2, 3, 4, 5], k = 4

Output: 3

Explanation: The value 4 is located at index 3 in the array. Since there is only one occurrence of 4, index 3 is the answer.

Example 2

Input: arr = [11, 22, 33, 44, 55], k = 445

Output: -1

Explanation: The value 445 does not exist anywhere in the array. No index can be returned, so the answer is -1.

Example 3

Input: arr = [1, 1, 1, 1, 2], k = 1

Output: 0

Explanation: The value 1 appears at indices 0, 1, 2, and 3. Since the problem asks for the smallest index, the answer is 0.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^6
  • 1 ≤ k ≤ 10^6
  • The array arr[] is sorted in non-decreasing order

Editorial

Brute Force

Intuition

The most straightforward way to search for a value in an array is to check every element from left to right. You start at the beginning, look at each element one by one, and ask: "Is this the value I am looking for?" If you find it, you return its index. If you reach the end without finding it, the value is not in the array.

Think of it like searching for a specific book on a long bookshelf by starting at the leftmost book and sliding your finger along each book title until you find the one you want. You do not skip any book — you check each one in order.

Since we need the smallest index when duplicates exist, scanning from left to right naturally handles this: the first match we encounter is guaranteed to be the leftmost occurrence.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 5], k = 4:

Step 1: Start at index 0. Check arr[0] = 1.

  • Is 1 == 4? No. Move to the next element.

Step 2: Check arr[1] = 2.

  • Is 2 == 4? No. Move to the next element.

Step 3: Check arr[2] = 3.

  • Is 3 == 4? No. Move to the next element.

Step 4: Check arr[3] = 4.

  • Is 4 == 4? YES! We found the target.

Step 5: Return index 3.

Result: 3

Linear Search — Scanning Every Element — Watch how linear search checks each element sequentially from left to right until it finds the target or exhausts the array.

Algorithm

  1. Iterate through the array from index 0 to n-1
  2. For each element arr[i], check if arr[i] == k
  3. If a match is found, return i immediately (this gives the smallest index since we scan left to right)
  4. If the loop completes without finding k, return -1

Code

class Solution {
public:
    int binarysearch(vector<int>& arr, int k) {
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            if (arr[i] == k) {
                return i;
            }
        }
        return -1;
    }
};
class Solution:
    def binarysearch(self, arr, k):
        n = len(arr)
        for i in range(n):
            if arr[i] == k:
                return i
        return -1
class Solution {
    public int binarysearch(int[] arr, int k) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == k) {
                return i;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, the target is at the last position or not present at all, requiring us to check every single element. With n up to 10^5, this means up to 100,000 comparisons.

Space Complexity: O(1)

We only use a single loop variable. No additional data structures are needed.

Why This Approach Is Not Efficient

Linear search completely ignores the most important property of the input: the array is sorted. When data is sorted, we have information about the relative ordering of elements — if we look at any element and it is smaller than our target, then every element to its left is also smaller. Conversely, if an element is larger than our target, every element to its right is also larger.

Linear search treats sorted data the same as unsorted data, checking elements one by one. With n up to 10^5, this means up to 100,000 comparisons in the worst case.

The key insight is: by looking at the middle element, we can determine which half of the array the target must be in, and discard the other half entirely. This halving strategy reduces the search space exponentially — from n to n/2 to n/4 ... to 1 — requiring only about log₂(n) comparisons. For n = 10^5, that is roughly 17 comparisons instead of 100,000.

Optimal Approach - Binary Search

Intuition

Imagine you are looking for a word in a physical dictionary. You would never start from page 1 and read every page sequentially. Instead, you would open the dictionary roughly in the middle, check if your word comes before or after that page, and then focus on the correct half. You keep halving the remaining pages until you find your word.

Binary search works exactly the same way. We maintain two pointers — low and high — that define the current search range. We compute the middle index, compare the middle element with the target:

  • If arr[mid] == k, we found a match. But since the problem asks for the smallest index, we cannot stop immediately — there may be duplicate occurrences of k to the left. So we record this index as a candidate answer and continue searching in the left half (set high = mid - 1).
  • If arr[mid] < k, the target must be in the right half (set low = mid + 1).
  • If arr[mid] > k, the target must be in the left half (set high = mid - 1).

We repeat until low > high, meaning the search space is exhausted. The last recorded candidate index is our answer.

This "find leftmost" variant is critical for this problem — a standard binary search that returns immediately upon finding k would not guarantee the smallest index when duplicates exist.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 5], k = 4:

Step 1: Initialize low = 0, high = 4, result = -1.

  • Search range: [1, 2, 3, 4, 5] (entire array).

Step 2: Compute mid = 0 + (4 - 0) / 2 = 2. Check arr[2] = 3.

  • Is 3 == 4? No.
  • Is 3 < 4? Yes. The target must be in the right half.
  • Set low = mid + 1 = 3.

Step 3: Compute mid = 3 + (4 - 3) / 2 = 3. Check arr[3] = 4.

  • Is 4 == 4? Yes! Found a match.
  • Record result = 3. Since we want the smallest index, search the left half for earlier occurrences.
  • Set high = mid - 1 = 2.

Step 4: Now low = 3 > high = 2. Search space is empty. Stop.

Step 5: Return result = 3. No earlier occurrence existed.

Result: 3

Now let's also trace the case with duplicates: arr = [1, 1, 1, 1, 2], k = 1:

Step 1: low = 0, high = 4, result = -1.

Step 2: mid = 2. arr[2] = 1 == 1. Match! Record result = 2. Search left: high = 1.

Step 3: mid = 0. arr[0] = 1 == 1. Match! Record result = 0. Search left: high = -1.

Step 4: low = 0 > high = -1. Stop.

Result: 0 (the leftmost occurrence).

Binary Search — Halving the Search Space — Watch how binary search repeatedly picks the middle element and eliminates half the search space, finding the target in logarithmic time.

Algorithm

  1. Initialize low = 0, high = n - 1, result = -1
  2. While low ≤ high:
    a. Compute mid = low + (high - low) / 2 (avoids integer overflow)
    b. If arr[mid] == k:
    • Record result = mid (potential answer)
    • Set high = mid - 1 (search left half for an earlier occurrence)
      c. Else if arr[mid] < k:
    • Set low = mid + 1 (target is in the right half)
      d. Else (arr[mid] > k):
    • Set high = mid - 1 (target is in the left half)
  3. Return result

Code

class Solution {
public:
    int binarysearch(vector<int>& arr, int k) {
        int low = 0, high = arr.size() - 1;
        int result = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == k) {
                result = mid;
                high = mid - 1; // search left for smallest index
            } else if (arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return result;
    }
};
class Solution:
    def binarysearch(self, arr, k):
        low, high = 0, len(arr) - 1
        result = -1
        
        while low <= high:
            mid = low + (high - low) // 2
            
            if arr[mid] == k:
                result = mid
                high = mid - 1  # search left for smallest index
            elif arr[mid] < k:
                low = mid + 1
            else:
                high = mid - 1
        
        return result
class Solution {
    public int binarysearch(int[] arr, int k) {
        int low = 0, high = arr.length - 1;
        int result = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == k) {
                result = mid;
                high = mid - 1; // search left for smallest index
            } else if (arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each step, we halve the search space. Starting with n elements, after one comparison we have n/2 elements, then n/4, then n/8, and so on. The number of halvings needed to reduce n to 1 is log₂(n). For n = 10^5, this is approximately 17 comparisons — a dramatic improvement over linear search's 10^5 comparisons.

Even though we continue searching after finding a match (to find the leftmost occurrence), each continuation still halves the remaining space, so the total remains O(log n).

Space Complexity: O(1)

We use only a constant number of variables: low, high, mid, and result. No recursion stack or auxiliary data structures are needed in this iterative approach.