- Efficient way to search in sorted array.
- Find first and last occurence.
- Binary search STL (binary_search(arr,arr+n,key)) in algorithm header file.
- sort(a,a+n) [Quite efficient]
- Comparator:
- Make a compare function.
- sort(a,a+n,compare)
- Divide
- Sort
- Merge
- Divide and conquer algorithm
- Divide and conquer algorithm.
- Choose an eleemnt as pivot element.
- Divide in two parts(elements which are less than or equal to pivot, elements that are greater than pivot).
- Pivot will come in the correct position.
- Recursively sort the two parts.
- When we have data which lies in a certain range.
- Continuous element
- This involves three nested loops.
- Find subarray which has the max sum.
- Method 1: Generate sum for all the subarrays, keep updating the maxsum. O(n^3)
- Method 2: Using cummulative sum.
- csum[i] = csum[i-1] + a[i] (generated in linear time)
- for(i) for(j>=i) sum of array (i,j)= cs[j] - cs[j-i]
- It will take O(n^2) time.
- Method 3: Kadane's Algo! O(n)
Given a sorted array, find pair of elements that sum to k.
- Other method:
- Reverse all the rows. STL also have reverse method.
- Take transpose.
- Approach 1: *