Template that works for ALL binary search problems
password
URL
type
status
date
slug
summary
tags
category
icon
Binary Search - LeetCode
Can you solve this real interview question? Binary Search - Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.   Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 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: * 1 <= nums.length <= 104 * -104 < nums[i], target < 104 * All the integers in nums are unique. * nums is sorted in ascending order.
Binary Search - LeetCode
https://leetcode.com/problems/binary-search
Binary Search - LeetCode
Find a template for binary search, without doubt about less than or equal to, return low or low + 1, just replace the condition for specific issue.

ATTENTION

  • The condition is written to minimize or maximize the result. For example, if you're looking for the first element that satisfies a property, you would write the condition to check if nums[mid] >= target.
  • The binary search will return the leftmost position where the condition is true (or the rightmost if modified for that use case).

Example

Find the first element in the array that is greater than or equal to target.