Binary Search

21 min read Searching LeetCode ↗ Step through the code →

On this page

Given a sorted (ascending) integer array nums of n elements and a target value target, write a function that searches for target in nums. Return its index if the target exists, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 appears in nums at index 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums, so return -1

Constraints:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
Every element of nums will be in the range [-9999, 9999].

Approach#

The precondition for this problem is that the array is sorted, and the problem also emphasizes that the array contains no duplicate elements. Once duplicates exist, the index returned by binary search may not be unique. These are the prerequisites for using binary search — whenever you see a problem description that satisfies these conditions, it’s worth asking yourself whether binary search applies.

Binary search involves a lot of boundary conditions. The logic is fairly simple, yet people still can’t get it right. For example: should it be while (left < right) or while (left <= right)? Should it be right = mid or right = mid - 1?

The reason people keep muddling binary search is that they haven’t thought clearly about the definition of the interval — and the definition of the interval is the invariant: the one statement you keep true on every iteration. To keep that invariant during the search, every boundary update inside the while loop must be handled according to the interval’s definition. That is the loop invariant rule.

When writing binary search, there are generally two ways to define the interval: closed on both ends, [left, right], or closed on the left and open on the right, [left, right).

Below I’ll explain two different ways to write binary search, one for each of these interval definitions.

Binary search, first version#

In the first version, we define target as living in an interval that is closed on both ends — that is, [left, right] (this is important, very important).

The definition of the interval determines how the code must be written. Because target is defined to be in [left, right], the following two points hold:

while (left <= right) must use <=, because left == right is meaningful, so we use <=
When if (nums[mid] > target), right must be assigned mid - 1, because this nums[mid] is definitely not the target, so the end index of the left interval we search next is mid - 1

For example, searching for the element 2 in the array 1,2,3,4,7,9,10, as shown below:

One step of the closed-interval search. right lands on mid - 1, because nums[mid] has already been ruled out.

In pseudocode, with the boundary handling called out:

left  = 0
// closed interval: target is in [left, right]
right = n - 1

// left == right is a valid interval, so <=
while left <= right:
    // overflow-safe
    mid = left + (right - left) / 2

    if nums[mid] > target:
        // mid ruled out: [left, mid - 1]
        right = mid - 1
    else if nums[mid] < target:
        // mid ruled out: [mid + 1, right]
        left = mid + 1
    else:
        // found it
        return mid

// interval emptied, no match
return -1

Time complexity: O(log n)
Space complexity: O(1)

This first version is the one worth committing to memory — it’s the template the interactive binary search snippet builds up line by line, in eight languages. The snippet names the bounds lo and hi rather than left and right, but it is the same closed-interval algorithm.

Binary search, second version#

If instead we define target as living in an interval closed on the left and open on the right — that is, [left, right) — then the boundary handling is completely different.

The two points are:

while (left < right), using < here, because left == right is meaningless in the interval [left, right)
When if (nums[mid] > target), right is updated to mid, because the current nums[mid] is not equal to target, so we continue searching the left interval; since the search interval is closed on the left and open on the right, right is updated to mid — meaning the next search interval will not compare nums[mid]

Searching for the element 2 in the array 1,2,3,4,7,9,10, as shown below (note the difference from the first approach):

The same step with a half-open interval. right lands on mid, because the right end is never read — so nums[mid] is still excluded.

In pseudocode, with the boundary handling called out:

left  = 0
// half-open: right is one past the end
right = n

// left == right is empty, so <
while left < right:
    // overflow-safe
    mid = left + (right - left) / 2

    if nums[mid] > target:
        // mid ruled out, becomes the open end
        right = mid
    else if nums[mid] < target:
        // mid ruled out: [mid + 1, right)
        left = mid + 1
    else:
        // found it
        return mid

// interval emptied, no match
return -1

Time complexity: O(log n)
Space complexity: O(1)

Summary#

Binary search is an extremely important fundamental algorithm. So why is it that for so many students, binary search is obvious the moment you look at it, and a disaster the moment you write it?

The main reason is really that they haven’t clearly understood the definition of the interval, and inside the loop they don’t consistently handle the boundaries according to that definition of the search interval.

The definition of the interval is the invariant. Consistently handling the boundaries in the loop according to the definition of the search interval is the loop invariant rule.

Based on the two common interval definitions, this article gives two ways of writing binary search, and explains in detail why each boundary is handled the way it is, according to the interval definition.

I’m confident that after reading this you’ll have a deeper understanding of binary search.

Implementations#

Both interval conventions, in every language. Pick yours from the list — the choice is remembered as you move around the site.

Language

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size() - 1; // define target to be in the closed interval [left, right]
        while (left <= right) { // when left == right, the interval [left, right] is still valid, so use <=
            int middle = left + ((right - left) / 2);// prevents overflow; equivalent to (left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target is in the left interval, so [left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target is in the right interval, so [middle + 1, right]
            } else { // nums[middle] == target
                return middle; // found the target in the array, return the index directly
            }
        }
        // target not found
        return -1;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // define target to be in the half-open interval [left, right)
        while (left < right) { // because when left == right, [left, right) is an invalid (empty) space, so use <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target is in the left interval, in [left, middle)
            } else if (nums[middle] < target) {
                left = middle + 1; // target is in the right interval, in [middle + 1, right)
            } else { // nums[middle] == target
                return middle; // found the target in the array, return the index directly
            }
        }
        // target not found
        return -1;
    }
};

class Solution {
    public int search(int[] nums, int target) {
        // avoids extra loop iterations when target is less than nums[0] or greater than nums[nums.length - 1]
        // (the length check must come first, or an empty array would throw here)
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid - 1;
            }
        }
        // target not found
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid;
            }
        }
        // target not found
        return -1;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # define target to be in the closed interval [left, right]

        while left <= right:
            middle = left + (right - left) // 2
            
            if nums[middle] > target:
                right = middle - 1  # target is in the left interval, so [left, middle - 1]
            elif nums[middle] < target:
                left = middle + 1  # target is in the right interval, so [middle + 1, right]
            else:
                return middle  # found the target in the array, return the index directly
        return -1  # target not found

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # define target to be in the half-open interval [left, right)

        while left < right:  # because when left == right, [left, right) is an invalid (empty) space, so use <
            middle = left + (right - left) // 2

            if nums[middle] > target:
                right = middle  # target is in the left interval, in [left, middle)
            elif nums[middle] < target:
                left = middle + 1  # target is in the right interval, in [middle + 1, right)
            else:
                return middle  # found the target in the array, return the index directly
        return -1  # target not found

// Time complexity O(logn)
func search(nums []int, target int) int {
	// initialize the left and right boundaries
	left := 0
	right := len(nums) - 1

	// loop, narrowing the interval step by step
	for left <= right {
		// find the midpoint of the interval
		mid := left + (right-left)>>1

		// adjust the interval based on the relationship
		// between nums[mid] and target
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	// no element equal to target was found in the input array
	return -1
}

// Time complexity O(logn)
func search(nums []int, target int) int {
	// initialize the left and right boundaries
	left := 0
	right := len(nums)

	// loop, narrowing the interval step by step
	for left < right {
		// find the midpoint of the interval
		mid := left + (right-left)>>1

		// adjust the interval based on the relationship
		// between nums[mid] and target
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}

	// no element equal to target was found in the input array
	return -1
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // right is the index of the last element of the array; nums[right] is within the search range, so this is a closed interval
    let mid, left = 0, right = nums.length - 1;
    // when left == right, nums[right] is still within the search range, so this case must be included
    while (left <= right) {
        // bit shift + prevents overflow on large numbers
        mid = left + ((right - left) >> 1);
        // if the middle value is greater than the target, the middle value must be excluded from the search range, so the right boundary is updated to mid-1; if the right boundary were updated to mid, the middle value would still be in the next search range
        if (nums[mid] > target) {
            right = mid - 1;  // search the left closed interval
        } else if (nums[mid] < target) {
            left = mid + 1;   // search the right closed interval
        } else {
            return mid;
        }
    }
    return -1;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // right is the index of the last element of the array plus 1; nums[right] is not within the search range, so this is a half-open interval
    let mid, left = 0, right = nums.length;    
    // when left == right, nums[right] is not within the search range, so this case need not be included
    while (left < right) {
        // bit shift + prevents overflow on large numbers
        mid = left + ((right - left) >> 1);
        // if the middle value is greater than the target, the middle value should not be in the next search range, but the value before it should be;
        // since right is already outside the search range, update the right boundary to the middle value — updating it to mid-1 would also kick the value before the middle out of the next search range
        if (nums[mid] > target) {
            right = mid;  // search the left interval
        } else if (nums[mid] < target) {
            left = mid + 1;   // search the right interval
        } else {
            return mid;
        }
    }
    return -1;
};

function search(nums: number[], target: number): number {
    let mid: number, left: number = 0, right: number = nums.length - 1;
    while (left <= right) {
        // bit shift + prevents overflow on large numbers
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

function search(nums: number[], target: number): number {
    let mid: number, left: number = 0, right: number = nums.length;
    while (left < right) {
        // bit shift + prevents overflow on large numbers
        mid = left +((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

# (Version one) closed interval [left, right]

def search(nums, target)
  left, right = 0, nums.length - 1
  while left <= right	# since target is defined to be in a closed interval, in the limiting case left == right can occur
    middle = (left + right) / 2
    if nums[middle] > target
      right = middle - 1
    elsif nums[middle] < target
      left = middle + 1
    else
      return middle	# return both returns the value and breaks out of the loop
    end
  end
  -1
end

# (Version two) half-open interval [left, right)

def search(nums, target)
  left, right = 0, nums.length
  while left < right	# since target is defined to be in a half-open interval, in the limiting case right = left + 1
    middle = (left + right) / 2
    if nums[middle] > target
      right = middle
    elsif nums[middle] < target
      left = middle + 1
    else
      return middle
    end
  end
  -1
end

// (Version one) closed interval [left, right]
func search(nums: [Int], target: Int) -> Int {
    // 1. First define the interval. The interval here is [left, right]
    var left = 0
    var right = nums.count - 1

    while left <= right {// because target is in [left, right], including both boundary values, left == right is meaningful here
        // 2. Compute the index of the middle of the interval (if left and right are both large, left + right could overflow)
        // let middle = (left + right) / 2
        // Overflow-safe:
         let middle = left + (right - left) / 2

        // 3. Compare
        if target < nums[middle] {
            // when the target is on the left side of the interval, we need to update the right boundary; the new interval is [left, middle - 1]
            right = middle - 1
        } else if target > nums[middle] {
            // when the target is on the right side of the interval, we need to update the left boundary; the new interval is [middle + 1, right]
            left = middle + 1
        } else { 
            // when the target is exactly in the middle, return the index of the middle value
            return middle
        }
    }

    // if the target can't be found, return -1
    return -1
}

// (Version two) half-open interval [left, right)
func search(nums: [Int], target: Int) -> Int {
    var left = 0
    var right = nums.count

    while left < right {
        let middle = left + ((right - left) >> 1)

        if target < nums[middle] {
            right = middle
        } else if target > nums[middle] {
            left = middle + 1
        } else {
            return middle
        }
    }

    return -1
}

use std::cmp::Ordering;
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left, mut right) = (0_i32, nums.len() as i32 - 1);
        while left <= right {
            let mid = left + (right - left) / 2; // overflow-safe midpoint
            match nums[mid as usize].cmp(&target) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid - 1,
                Ordering::Equal => return mid,
            }
        }
        -1
    }
}

use std::cmp::Ordering;
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left, mut right) = (0_i32, nums.len() as i32);
        while left < right {
            let mid = left + (right - left) / 2; // overflow-safe midpoint
            match nums[mid as usize].cmp(&target) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid,
                Ordering::Equal => return mid,
            }
        }
        -1
    }
}

// (Version one) closed interval [left, right]
int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    int middle = 0;
    // if left is less than or equal to right, the interval contains a non-zero number of elements
    while(left<=right) {
        // update the value of the search index middle (overflow-safe)
        middle = left + (right - left) / 2;
        // at this point target may be in the interval [left, middle-1]
        if(nums[middle] > target) {
            right = middle-1;
        } 
        // at this point target may be in the interval [middle+1, right]
        else if(nums[middle] < target) {
            left = middle+1;
        } 
        // when the element at the current index equals target, return middle
        else if(nums[middle] == target){
            return middle;
        }
    }
    // if the target element isn't found, return -1
    return -1;
}

// (Version two) half-open interval [left, right)
int search(int* nums, int numsSize, int target){
    int length = numsSize;
    int left = 0;
    int right = length;	// define target to be in the half-open interval, i.e. [left, right)
    int middle = 0;
    while(left < right){  // when left == right, the interval [left, right) is the empty set, so use < to avoid that case
        int middle = left + (right - left) / 2;
        if(nums[middle] < target){
            // target lies in (middle, right); to preserve the half-open property of the interval, this is equivalent to [middle + 1, right)
            left = middle + 1;
        }else if(nums[middle] > target){
            // target lies in [left, middle)
            right = middle ;
        }else{	// nums[middle] == target — the target has been found
            return middle;
        }
    }
    // target not found, return -1
    return -1;
}

// closed interval [left, right]
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        if (count($nums) == 0) {
            return -1;
        }
        $left = 0;
        $right = count($nums) - 1;
        while ($left <= $right) {
            $mid = floor(($left + $right) / 2);
            if ($nums[$mid] == $target) {
                return $mid;
            }
            if ($nums[$mid] > $target) {
                $right = $mid - 1;
            }
            else {
                $left = $mid + 1;
            }
        }
        return -1;
    }
}

// closed interval
public class Solution {  
    public int Search(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        while(left <= right){
            int mid = (right - left ) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
        }
        return -1;
    }
}

// half-open interval
public class Solution{
    public int Search(int[] nums, int target){
        int left = 0;
        int right = nums.Length;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid;
            }
        }
        return -1;
    }
}

// (Version one) half-open interval [left, right)
class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size // [left,right) — the right side is open, so right is set to nums.size
        while (left < right) {
            val mid = left + (right - left) / 2 // overflow-safe midpoint
            if (nums[mid] < target) left = mid + 1
            else if (nums[mid] > target) right = mid // the heart of the code: right is open in the loop, so it should be open here too
            else return mid
        }
        return -1 // target not found, return -1
    }
}

// (Version two) closed interval [left, right]
class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1 // [left,right] — the right side is closed, so right is set to nums.size - 1
        while (left <= right) {
            val mid = left + (right - left) / 2 // overflow-safe midpoint
            if (nums[mid] < target) left = mid + 1
            else if (nums[mid] > target) right = mid - 1 // the heart of the code: right is closed in the loop, so it should be closed here too
            else return mid
        }
        return -1 // target not found, return -1
    }
}

object Solution {
  def search(nums: Array[Int], target: Int): Int = {
    var left = 0
    var right = nums.length - 1
    while (left <= right) {
      var mid = left + ((right - left) / 2)
      if (target == nums(mid)) {
        return mid
      } else if (target < nums(mid)) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    -1
  }
}

object Solution {
  def search(nums: Array[Int], target: Int): Int = {
    var left = 0
    var right = nums.length
    while (left < right) {
      val mid = left + (right - left) / 2
      if (target == nums(mid)) {
        return mid
      } else if (target < nums(mid)) {
        right = mid
      } else {
        left = mid + 1
      }
    }
    -1
  }
}

class Solution {
  int search(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
      int middle = ((left + right)/2).truncate();
      switch (nums[middle].compareTo(target)) {
        case 1:
          right = middle - 1;
          continue;
        case -1:
          left = middle + 1;
          continue;
        default:
          return middle;
      }
    }
    return -1;
  }
}

class Solution {
  int search(List<int> nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
      int middle = left + ((right - left) >> 1);
      switch (nums[middle].compareTo(target)) {
        case 1:
          right = middle;
          continue;
        case -1:
          left = middle + 1;
          continue;
        default:
          return middle;
      }
    }
    return -1;
  }
}

Practice — 6 Grind 75 problems

Easy 2

Easy Binary Search Step through →
Easy First Bad Version

Medium 2

Medium Search in Rotated Sorted Array
Medium Time Based Key-Value Store also Advanced Data Structures

Related from other patterns 2

Going further

These aren't part of Grind 75, so the bot won't schedule them. They're the natural next problems once the loop invariant makes sense — each one bends the same template to a slightly different question.

35. Search Insert Position LeetCode ↗
34. Find First and Last Position of Element in Sorted Array LeetCode ↗
69. Sqrt(x) LeetCode ↗
367. Valid Perfect Square LeetCode ↗