Notes on Fenwick tree

The Fenwick tree is more popularly known as the Binary Indexed Tree which works solves the Range Sum Queries problems. The same can be achieved by a Segment Tree or a RMQ but the BIT wins big time in terms of simplicity. It server two primary queries: Update index I by value V Get sum …

More

Find minimum element in rotated sorted array – Modified binary search

Here is small snippet to find minimum element in rotated sorted array. The code uses a modified binary search to search the element from the array.   package search; public class RotatedArray { static int arr[] ={7,8,9,10,11,13,24,1,2,3,4,5,6}; public static int search(int low, int high){ if(low>high) return -1; if(arr[low]>arr[high]){ int mid = (low+high)/2; if(arr[mid]>arr[high]) return search(mid+1,high); …

More