Binary Search Tree is a node-based binary tree data structure that has the following properties:
When we are talking about the average case, it is the time it takes for the operation on a balanced tree, and when we are talking about the worst case, it is the time it takes for the given operation on a non-balanced tree.
Operations | Worst Case | Average Case | Best Case |
Insert | O(n) | O(log n) | O(1) |
Delete | O(n) | O(log n) | O(1) |
Search | O(n) | O(log n) | O(1) |
The equation T(n)= T(n/2)+1 is known as the recurrence relation for binary search.
To perform binary search time complexity analysis, we apply the Master Theorem to the equation and get O(log n).
Below are the basic steps to performing Binary Search.
Applications of Binary tree:
LeetCode 704 - Binary Search [easy]
Given an array of integers nums
that 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
Solution:
class Solution:
def search(self, nums: List[int], target: int) -> int:
start = 0
end = len(nums)
while start < end:
mid = (end + start) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
end = mid
elif nums[mid] < target:
start = mid + 1
return -1
Time Complexity: O(log n) where n is the total elements in the given array. Space Complexity: O(1)
LeetCode 744. Find Smallest Letter Greater Than Target
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.
target == 'z'
and letters == ['a', 'b']
, the answer is 'a'
.Example 1: Input: letters = ["c","f","j"], target = "a" Output: "c"
Solution:
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left, right = 0, len(letters)-1
if target >= letters[right] or target < letters[left]:
return letters[0]
while left < right:
mid = (right + left) // 2
if target < letters[mid]:
right = mid
else:
left = mid + 1
return letters[right]