Check both possible neighbors for key
    in a binary tree
485028
def get_near_items(tree, tree_key):
    
    try:
        yield tree.floor_item(tree_key)
    except KeyError:
        pass
    try:
        yield tree.ceiling_item(tree_key)
    except KeyError:
        pass
441464
protected void checkBestDistance(KdTree.Node node, P target) {

		double distanceSq = distance.distance((P)node.point,target);
		// <= because multiple nodes could be at the bestDistanceSq
		if( distanceSq <= bestDistanceSq ) {

			// see if the node is already in the list.  This is possible because there can be multiple trees
			for( int i = 0; i < neighbors.size(); i++ ) {
				KdTreeResult r = neighbors.get(i);
				if( r.node.point == node.point )
					return;
			}

			if( neighbors.size() < searchN ) {
				// the list of nearest neighbors isn't full yet so it doesn't know what the distance will be
				// so just keep on adding them to the list until it is full
				KdTreeResult r = neighbors.grow();
				r.distance = distanceSq;
				r.node = node;
				if( neighbors.size() == searchN ) {

					// find the most distant node
					bestDistanceSq = 0;
					for( int i = 0; i < searchN; i++ ) {
						r = neighbors.get(i);

						if( r.distance > bestDistanceSq ) {
							bestDistanceSq = r.distance;
						}
					}
				}
			} else {
				// find the most distant neighbor and write over it since we known this node must be closer
				// and update the maximum distance
				for( int i = 0; i < searchN; i++ ) {
					KdTreeResult r = neighbors.get(i);
					if( r.distance == bestDistanceSq ) {
						r.node = node;
						r.distance = distanceSq;
						break;
					}
				}

				// If there are multiple points then there can be more than one point with the value of
				// 'bestDistanceSq', which is why two searches are required
				bestDistanceSq = 0;
				for( int i = 0; i < searchN; i++ ) {
					KdTreeResult r = neighbors.get(i);
					if( r.distance > bestDistanceSq ) {
						bestDistanceSq = r.distance;
					}
				}
			}
		}
	}
1258468
public static int findEdge(Poly node, Poly neighbour, MeshData tile, MeshData neighbourTile) {
		// Compare indices first assuming there are no duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((node.verts[i] == neighbour.verts[l] && node.verts[j] == neighbour.verts[k])
						|| (node.verts[i] == neighbour.verts[k] && node.verts[j] == neighbour.verts[l])) {
					return i;
				}
			}
		}
		// Fall back to comparing actual positions in case of duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[l])
						&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[k]))
						|| (samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[k])
								&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[l]))) {
					return i;
				}
			}
		}
		return -1;
	}
40673
private int binarySearchNonUnique(int fromIndex, int toIndex, long key1, long key2) {
		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			long midVal1 = keys[mid];
			long midVal2 = values[mid];

        	if (midVal1 < key1) {
        		low = mid + 1;
        	} else if (midVal1 > key1) {
        		high = mid - 1;
        	} else {
            	if (midVal2 < key2) {
            		low = mid + 1;
            	} else if (midVal2 > key2) {
            		high = mid - 1;
            	} else {
            		return mid; // key found
            	}
        	}
		}
		return -(low + 1);  // key not found.
	}
440556
def _precompute(self, tree):
        
        d = {}
        for n in tree.preorder_internal_node_iter():
            d[n] = namedtuple('NodeDist', ['dist_from_root', 'edges_from_root'])
            if n.parent_node:
                d[n].dist_from_root = d[n.parent_node].dist_from_root + n.edge_length
                d[n].edges_from_root = d[n.parent_node].edges_from_root + 1
            else:
                d[n].dist_from_root = 0.0
                d[n].edges_from_root = 0
        return d
23056
private int binarySearch(SimpleMDAGNode[] mdagDataArray, char node)
    {
        if (transitionSetSize < 1)
        {
            return -1;
        }
        int high = transitionSetBeginIndex + transitionSetSize - 1;
        int low = transitionSetBeginIndex;
        while (low <= high)
        {
            int mid = ((low + high) >>> 1);
            int cmp = mdagDataArray[mid].getLetter() - node;

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
    }
1210348
private void search(double[] q, Node node, Neighbor<double[], E> neighbor) {
        if (node.isLeaf()) {
            // look at all the instances in this leaf
            for (int idx = node.index; idx < node.index + node.count; idx++) {
                if (q == keys[index[idx]] && identicalExcluded) {
                    continue;
                }

                double distance = Math.squaredDistance(q, keys[index[idx]]);
                if (distance < neighbor.distance) {
                    neighbor.key = keys[index[idx]];
                    neighbor.value = data[index[idx]];
                    neighbor.index = index[idx];
                    neighbor.distance = distance;
                }
            }
        } else {
            Node nearer, further;
            double diff = q[node.split] - node.cutoff;
            if (diff < 0) {
                nearer = node.lower;
                further = node.upper;
            } else {
                nearer = node.upper;
                further = node.lower;
            }

            search(q, nearer, neighbor);

            // now look in further half
            if (neighbor.distance >= diff * diff) {
                search(q, further, neighbor);
            }
        }
    }
1288224
@Override
	public KdTree.Node findNeighbor(P target) {
		if( tree.root == null )
			return null;

		this.target = target;
		this.closest = null;
		this.bestDistanceSq = maxDistanceSq;

		stepClosest(tree.root);

		return closest;
	}
74816
private void checkTree(int t) {
    int head = -1;
    int u = t;
    int tindex = index(t);
    int tsize = chunkSize(t);
    int index = treeBinIndex(tsize);

    if (tindex != index) 
      throw new AssertionError("Tree node " + u + " has incorrect index [" + index(u) + "!=" + tindex + "]");
    if (tsize < MIN_LARGE_SIZE)
      throw new AssertionError("Tree node " + u + " is too small to be in a tree [" + tsize + "<" + MIN_LARGE_SIZE + "]");
    if (tsize < minSizeForTreeIndex(index))
      throw new AssertionError("Tree node " + u + " is too small to be in this tree [" + tsize + "<" + minSizeForTreeIndex(index) + "]");
    if (index != NTREEBINS-1 && tsize >= minSizeForTreeIndex(index + 1))
      throw new AssertionError("Tree node " + u + " is too large to be in this tree [" + tsize + ">=" + minSizeForTreeIndex(index + 1) + "]");

    do { /* traverse through chain of same-sized nodes */
      checkAnyChunk(u);
      if (index(u) != tindex)
        throw new AssertionError("Tree node " + u + " has incorrect index [" + index(u) + "!=" + tindex + "]");
      if (chunkSize(u) != tsize)
        throw new AssertionError("Tree node " + u + " has an mismatching size [" + chunkSize(u) + "!=" + tsize + "]");
      if (isInUse(u))
        throw new AssertionError("Tree node " + u + " is in use");
      if (nextPreviousInUse(u))
        throw new AssertionError("Tree node " + u + " is marked as in use in the next chunk");
      if (backward(forward(u)) != u)
        throw new AssertionError("Tree node " + u + " has incorrect chain links");
      if (forward(backward(u)) != u)
        throw new AssertionError("Tree node " + u + " has incorrect chain links");
      if (parent(u) == -1 && u != treeBins[index]) {
        if (child(u, 0) != -1)
          throw new AssertionError("Tree node " + u + " is chained from the tree but has a child " + child(u, 0));
        if (child(u, 1) != -1)
          throw new AssertionError("Tree node " + u + " is chained from the tree but has a child" + child(u, 1));
      } else {
        if (head != -1)
          throw new AssertionError("Tree node " + u + " is the second node in this chain with a parent [first was " + head + "]");
        head = u;
        
        if (treeBins[index] == u) {
          if (parent(u) != -1)
            throw new AssertionError("Tree node " + u + " is the head of the tree but has a parent " + parent(u));
        } else {
          if (parent(u) == u)
            throw new AssertionError("Tree node " + u + " is its own parent");
          if (child(parent(u), 0) != u && child(parent(u), 1) != u)
            throw new AssertionError("Tree node " + u + " is not a child of its parent");
        }
        
        if (child(u, 0) != -1) {
          if (parent(child(u, 0)) != u)
            throw new AssertionError("Tree node " + u + " is not the parent of its left child");
          if (child(u, 0) == u)
            throw new AssertionError("Tree node " + u + " is its own left child");
          checkTree(child(u, 0));
        }
        if (child(u, 1) != -1) {
          if (parent(child(u, 1)) != u)
            throw new AssertionError("Tree node " + u + " is not the parent of its right child");
          if (child(u, 1) == u)
            throw new AssertionError("Tree node " + u + " is its own right child");
          checkTree(child(u, 1));
        }
        if (child(u, 0) != -1 && child(u, 1) != -1 && chunkSize(child(u, 0)) >= chunkSize(child(u, 1))) {
          throw new AssertionError("Tree node " + u + " has it's left child bigger than it's right child");
        }
      }
      u = forward(u);
    } while (u != t);
    
    if (head == -1)
      throw new AssertionError("This tree level has no nodes with a parent");
  }
827657
@SuppressWarnings("unchecked")
    private void comparableDecreaseKey(Node<K, V> n, K newKey) {
        int c = ((Comparable<? super K>) newKey).compareTo(n.key);
        if (c > 0) {
            throw new IllegalArgumentException("Keys can only be decreased!");
        }
        n.key = newKey;
        if (c == 0) {
            return;
        }

        if (n.next == null) {
            throw new IllegalArgumentException("Invalid handle!");
        }

        // if not root and heap order violation
        Node<K, V> y = n.parent;
        if (y != null && ((Comparable<? super K>) n.key).compareTo(y.key) < 0) {
            cut(n, y);
            root.mark = false;
            cascadingRankChange(y);
            if (((Comparable<? super K>) n.key).compareTo(root.key) < 0) {
                root = link(root, n);
            } else {
                link(n, root);
            }
        }
    }
1081693
static int binarySearch(final boolean[] a, final boolean key) {
        if (N.isNullOrEmpty(a)) {
            return N.INDEX_NOT_FOUND;
        }

        if (a[0] == key) {
            return 0;
        } else if (a[a.length - 1] != key) {
            return N.INDEX_NOT_FOUND;
        }

        int left = 0, right = a.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (a[mid] == key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
868270
private V getBest(int t, ByteBuffer b, int offset, int len) {
        int node = t;
        int o = offset + b.position();

        loop:
        for (int i = 0; i < len; i++) {
            byte c = (byte) (b.get(o + i) & 0x7f);
            if (isCaseInsensitive())
                c = (byte) StringUtils.lowercases[c];

            while (true) {
                int row = ROW_SIZE * t;
                char n = _tree[row];
                int diff = n - c;

                if (diff == 0) {
                    t = _tree[row + EQ];
                    if (t == 0)
                        break loop;

                    // if this node is a match, recurse to remember
                    if (_key[t] != null) {
                        node = t;
                        V best = getBest(t, b, offset + i + 1, len - i - 1);
                        if (best != null)
                            return best;
                    }
                    break;
                }

                t = _tree[row + hilo(diff)];
                if (t == 0)
                    break loop;
            }
        }
        return (V) _value[node];
    }
137015
private void search(Node node, E q, int k, List<Neighbor<E, E>> neighbors) {
        int d = (int) distance.d(node.object, q);

        if (d <= k) {
            if (node.object != q || !identicalExcluded) {
                neighbors.add(new Neighbor<>(node.object, node.object, node.index, d));
            }
        }

        if (node.children != null) {
            int start = Math.max(1, d-k);
            int end = Math.min(node.children.size(), d+k+1);
            for (int i = start; i < end; i++) {
                Node child = node.children.get(i);
                if (child != null) {
                    search(child, q, k, neighbors);
                }
            }
        }
    }
985791
def neighbors(self, node_id):
        """"""
        node = self.get_node(node_id)
        return [self.get_edge(edge_id)['vertices'][1] for edge_id in node['edges']]
1149822
private void findNeighbor(int p) {
        // if no neighbors available, set flag for UpdatePoint to find
        if (npoints == 1) {
            neighbor[p] = p;
            distance[p] = Float.MAX_VALUE;
            return;
        }

        // find first point unequal to p itself
        int first = 0;
        if (p == points[first]) {
            first = 1;
        }

        neighbor[p] = points[first];
        distance[p] = linkage.d(p, neighbor[p]);

        // now test whether each other point is closer
        for (int i = first + 1; i < npoints; i++) {
            int q = points[i];
            if (q != p) {
                float d = linkage.d(p, q);
                if (d < distance[p]) {
                    distance[p] = d;
                    neighbor[p] = q;
                }
            }
        }
    }
12424
def _sparse_neighbor_graph(X, k, binary=False, metric='l2'):
  ''''''
  knn = NearestNeighbors(n_neighbors=k, metric=metric).fit(X)
  mode = 'connectivity' if binary else 'distance'
  try:
    adj = knn.kneighbors_graph(None, mode=mode)
  except IndexError:
    # XXX: we must be running an old (<0.16) version of sklearn
    #  We have to hack around an old bug:
    if binary:
      adj = knn.kneighbors_graph(X, k+1, mode=mode)
      adj.setdiag(0)
    else:
      adj = knn.kneighbors_graph(X, k, mode=mode)
  return Graph.from_adj_matrix(adj)
836011
private int rank(Key key, RedBlackTreeNode<Key, Value> x) {
	if (x == null)
	    return 0;
	int cmp = key.compareTo(x.getKey());
	if (cmp < 0)
	    return rank(key, x.getLeft());
	else if (cmp > 0)
	    return 1 + size(x.getLeft()) + rank(key, x.getRight());
	else
	    return size(x.getLeft());
    }