Binary Search DSA Solution - Classic Search - Study Chapter | QuizMaker

Binary Search explained with brute force, optimized halving approach, dry run, boundary rules, complexity, and Python, C++, Java code.

Read: 9m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 3: Binary Search

Learning Outcome

After this lesson, you should be able to explain why sorted order allows half the search space to be discarded at every step.

Problem Statement

Given a sorted integer array nums and a target, return the index of target. If the target is not present, return -1.

Input	Output	Why
`nums = [-1,0,3,5,9,12]`, `target = 9`	`4`	`nums[4]` is `9`.
`target = 2`	`-1`	`2` is not present.

Brute Force Approach

Scan from left to right until the target is found. This is easy, but it ignores sorted order and costs O(n).

Optimized Approach

Keep two boundaries: left and right. Check the middle index. If the middle value is too small, the target can only be on the right. If it is too large, the target can only be on the left.

The key is to move boundaries past mid, otherwise the loop may never shrink.

Exact Pseudocode

left = 0
right = length(nums) - 1
while left <= right:
  mid = left + (right - left) // 2
  if nums[mid] == target:
    return mid
  if nums[mid] < target:
    left = mid + 1
  else:
    right = mid - 1
return -1

Reference Code

class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Sample Dry Run

left	right	mid	nums[mid]	Action
0	5	2	3	3 < 9, move left to 3
3	5	4	9	Found target, return 4

Complexity

Measure	Value	Reason
Time	O(log n)	The search range is halved each step.
Space	O(1)	Only boundary variables are stored.

Edge Cases

Empty array or single element.
Target at first or last index.
Target absent and boundaries cross.

Interview Checklist

Confirm the array is sorted.
Use left + (right - left) / 2 for midpoint.
Move to mid + 1 or mid - 1, not just mid.

FAQs

Why use left <= right?

This closed-interval version keeps both ends searchable until the boundaries cross.

Why calculate mid this way?

It avoids overflow in languages where left + right can overflow.

What is the core pattern?

Halve a sorted search range using comparisons.