Data Structure

Arrays

Binary Search:

mid = low + (high - low)/2

Insertion in sorted array:

Ending condition - if low == high + low / 2 (Using binary search)

Find pair for the given sum:

• hash[sum - val(i)] = val(i)
• if val(i) in hash

Moores Voting Algorithm:

findCandidate(a[], size)

1. Initialize index and count of majority element maj_index = 0, count = 1
2. Loop for i = 1 to size – 1 (a) If a[maj_index] == a[i] count++ (b) Else count--; (c) If count == 0 maj_index = i; count = 1
3. Return a[maj_index]

Find missing number without duplicates:

n * (n + 1) / 2

Max to the right: