5 months

# Coding Patterns: Modified Binary Search

Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

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.

# Time Complexity of Binary Search 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.

1. Find the mid element of the whole array, as it would be the search key.
2. Look at whether or not the search key is equivalent to the item in the middle of the interval and return an index of that search key.
3. If the value of the middle item in the interval is more than the search key, reduce the interval’s lower half.
4. If the opposite, then lower the upper half.
5. Repeat from point 2, until the value is found or the interval gets empty.

Applications of Binary tree:

1. One of the most important application of binary trees is balanced binary search trees like Red-Black trees,AVL trees,Scapegoat trees.
2. Binary trees are used in Huffman coding, which are used as a compression code.
3. Binary trees are used in Binary search trees, which are useful for maintaining records of data without much extra space.
4. BST a kind of binary tree is used in Unix kernels for managing a set of virtual memory areas(VMAs).
5. Nearly all database (and database-like) programs use a binary tree to implement their indexing systems.

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 ComplexityO(log n) where n is the total elements in the given array.  Space ComplexityO(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.

• For example, if `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]

See all(3)

Tags

Topics
Related