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|
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:
Given an array of integers
nums that is sorted in ascending order, and an integer
target, write a function to search
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
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:
elif nums[mid] > target:
end = mid
elif nums[mid] < target:
start = mid + 1
Time Complexity: O(log n) where n is the total elements in the given array. Space Complexity: O(1)
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
Example 1: Input: letters = ["c","f","j"], target = "a" Output: "c"
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left, right = 0, len(letters)-1
if target >= letters[right] or target < letters[left]:
while left < right:
mid = (right + left) // 2
if target < letters[mid]:
right = mid
left = mid + 1