binary search

Definition A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height. Motivation behind Balanced Search tree Properties of sorted array Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]

For two sorted lists, 1, 2, 12, 15, 17, 18 1, 12, 14, 15, 16, 18, 20 intersection is bold numbers. Solution 1 : Brute force An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. [Read More]

There are two basic searching algorithms used. One is the simplest technique and is discussed here. Here we will discuss the binary search method. The other search method is the binary search method. The binary search technique is a very fast and a more efficient technique when compared to the linear search method, and gets us the result in O(log n) where n is number of elements. The only requirement for this method is that the input array of elements must be in the sorted order. [Read More]