Binary Search
Last updated
Last updated
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.
Example 1:
Example 2:
Constraints:
1 <= nums.length <= 10**4
-10**4 < nums[i], target < 10**4
All the integers in nums are unique.
nums
is sorted in ascending order.
Solution:
The searching space is always a closed interval: [low, high]
.
Loop condition is always while low <= high
.
The return value is always mid
.
Always use low = mid + 1
and high = mid - 1
.
If nums[mid]
have repeated values in nums
, determine its position according to nums[mid - 1]
and nums[mid + 1]
.
Handle the "hit" case first. For example, handle if nums[mid] == target
first, then elif nums[mid] < target
, then else
.
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1]
.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.
-109 <= target <= 109
Solution:
Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.
Note that the letters wrap around.
For example, if target == 'z'
and letters == ['a', 'b']
, the answer is 'a'
.
Example 1:
Example 2:
Example 3:
Constraints:
2 <= letters.length <= 10**4
letters[i]
is a lowercase English letter.
letters
is sorted in non-decreasing order.
letters
contains at least two different characters.
target
is a lowercase English letter.
Solution:
You must write an algorithm with runtime complexity.
You must write an algorithm with runtime complexity.