Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

for(int j=arrIndex/2 ; j < arrIndex;j++) …

shanky - Nov 0, 2014

for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}

This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i

Hi Shanky, you are right. That’s what I have done :)

search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach. Approach 2 : Club binary search approach and array’s random access property Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). [Read More]
search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Searching the element in sorted infinite array of integers

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question : Given an infinite array of integers which is sorted. How would you search for an integer in this array? Here is the algo (in java): public static int searchInf(int A,int high,int x){ // Assume we are searching for x if (A11 > x){ return -1; } if(Ahighhigh == x){ return high; } else{ int low = high; int higher = (int) Math.pow(2,high); if (Ahighhigh>x){ binarySearch(A,low,higher); } else{ searchInf(A,higher,x); } }// end else return -1; }// end searchInf method So if we find some element greater than element x, perform normal binary search, else call the search inf function. [Read More]
search  ArraySearch  kodeknight  sorting  binary search 

DFS (Depth First Search) on tree or graph

 Posted on January 1, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Consider this tree (which is a graph without a cycle) : Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem. A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. [Read More]
backtracking  Graph  search  tree  kodeknight  sorting  DFS  incomplete  traversal  binary-search-tree  BST  graph-search 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

def findMin(arr): print(“Finding min in a…

Anonymous - Sep 4, 2014

def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)

low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high

if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question : Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Trie : Searching in Trie

 Posted on October 9, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed. Consider the following TRIE as usual. The search alogirthm involves the following steps For each character in the string, see if there is a child node with that character as the content. If that character does not exist, return false If that character exist, repeat step 1. [Read More]
search  kodeknight  trie 

Balanced Search tree

 Posted on September 10, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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]
search  theory  tree  Binary Tree  BT  kodeknight  red-black-tree  RBT  balanced trees  time complexity  binary search  avl 

BST : Improving search by using sentinel

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A normal search across a BST (Binary Search Tree) would look like this bool BinaryTree::Search (int data ) { Node \*current = this\->root; while ( current != NULL ) { if (current->data < data) { current = current->left; } else if (current->data > data) { current = current->right; } else if ( current->data == data ) { return true; } } return false; } You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. [Read More]
search  tree  kodeknight  binary-search-tree  BST 

BK-Treesal

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

I am making my own vocab software. I provided words, meanings, synonyms, search. I feel the project is partially over. So now I thought, why not provide google-like “Did you mean” option in my search. So it all starts with this, I came closer to algorithms again. :) BK-Trees BK-Trees, or Burkhard-Keller Trees are a tree-based data structure engineered for quickly finding near-matches to a string, for example, as used by a spelling checker, or when doing a ‘fuzzy’ search for a term. [Read More]
search  Algorithms  kodeknight