- Sorted array is pre-condition for binary Search. Take two pinter with start = 0, end = n-1 where n is length of the array.
- Search a sorted array by repeatedly dividing the search interval in half.
- mid = (start + end) / 2
- Case 1: x == A[mid] return mid
- Case 2: x < A[mid] end = mid - 1 (x lies before the mid element, so shift end)
- Case 3: x > A[mid] start = mid + 1 (x lies after the mid element, so shift start)
- Continue till start <= end, (because even when start == end, we have 1 element to check)
If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
int binarySearch(int array[], int start, int end, int numberToFind);
Complexity: (n / 2^k) = 1, were k is no of steps to reach result, while n is length of array. This gives k = log n. Hence the time complexity is O(log n).
Recursive Version:
- binarySearch(array, start, end, numberToFind)
- When start > end, then return -1
- mid = (start + end) / 2
- Case 1: x == array[mid], then return mid
- Case 2: x < array[mid], then call binarySearch(array, start, mid-1, numberToFind)
- Case 3: x > array[mid], then call binarySearch(array, mid+1, end, numberToFind)
Binary Search - First Occurrence of the element
We have a sorted array with duplicate elements to find the first occurrence of the element.
Modify the Case1 as below:
result = -1 (initialize the result with -1 indicating that no match found)
Case 1: x == A[mid] then
result = mid; (capture the result i.e. the position of the matched element)
end = mid - 1 (to find first occurrence of the element x, check if there is one more occurrence of x before matched mid element, hence we shift end before mid)
Finally return result
Binary Search - Last Occurrence of the element
Similar to above we modify the Case1 as below:
Case 1: x == A[mid] then
result = mid; (capture the result i.e. the position of the matched element)
start = mid + 1 (to find last occurrence of the element x, check if there is one more occurrence of x after the matched mid element, hence we shift start after mid)
Finally return result
Time complexity of both these variations of binary search is O(log n).
Count number of occurrences of element in sorted array
Strategy 1: Loop through the sorted array until there is a match and count until there is no match.
Strategy 2: Find the element in the sorted array using binary search, then first shift left and then shift right to count all the occurrences of the element.
Strategy 3: Find the first occurrence of element using binary search and then the last occurrence of element using binary search, using that determine the count of occurrences since the array is sorted i.e. (Last - First + 1).
Search element in a circular sorted array
Given a sorted circular array were the start element followed by end element lies somewhere in the middle of the array.
E.g. 12, 14, 18, 21, 3, 6, 8, 9
low mid high
The start element in the above array is 3.
In the below code, x is the input element to be searched and we need to determine the position of x in the array.
mid = (low + high) / 2
Case1: A[mid] == x, return mid
Case2: A[mid] <= A[high] // Right half is sorted
2A: x > A[mid] && x <= A[high]
low = mid + 1 // search in right sorted half
Else
high = mid - 1 // search in left half
Case 3: A[low] <= A[mid] // Left half is sorted
3A: x >= A[low] && x < A[mid]
high = mid - 1 // search in left sorted half
Else
low = mid + 1 // search in right half
Precedence of Operators
(high + low) / 2 is same as low + ((high - low)/2), as low + high can overflow if range exceeds integer.
Memoization
Memoization is an optimization technique used to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Sorting
Quick Sort
It is in place sorting.
Average case: O(n log n)
Worst case: n pow 2
1) Select a Pivot.
2) Move the elements lower than pivot to left side, while move elements higher than pivot to right side.
In below example we select the pivot always as the last element.
QuickSort(A, start, end) {
if (start < end) {
pIndex = Partition(A, start, end)
QuickSort(A, start, pIndex-1)
QuickSort(A, pIndex+1, end)
}
}
Partition(A, start, end) {
pivot = A[end] // Pivot is always the last element of list
pIndex = start
for i=start to end-1 {
if(A[i] <= pivot) {
swap(A[i], A[pIndex])
pIndex = pIndex + 1
}
}
swap(A[pIndex], A[end])
return
}
Merge Sort
1) Split the list into half, at the mid point. Continue to split the 2 lists each recursively further until only 1 element is present.
2) Now merge all the splitted list earlier recursively from bottom up such that, the final list at each step is sorted. Note here while merging two lists, we first take original list which was splitted in those two lists in the first place. Loop through both the Left and Right splitter list to check which is greater/less and place them elements in sorted fashion into the original list. Repeat this for all list in each recursive step.
Merge(Left, Right, A) {
sizeLeft = length(Left)
sizeRight = length(Right)
i = j = k = 0
while(i < sizeLeft && j < sizeRight) {
if( Left[i] <= Right[j] ) {
A[k] = Left[i]
k = k + 1
i = i + 1
}
else {
A[k] = Right[j]
k = k + 1
j = j + 1
}
}
// If there are elements remaining in either Left or Right list then simply append to result list
while(i < sizeLeft) {
A[k] = Left[i]
i = i + 1
k = k + 1
}
while(j < sizeRight) {
A[k] = Right[j]
j = j + 1
k = k + 1
}
}
MergeSort(A) {
n = length(A)
if(n < 2) return
mid = n/2
left = array of size(mid)
right = array of size(n - mid)
for i = 0 to mid - 1
left[i] = A[i]
for i = mid to n - 1
right[i-mid] = A[i]
MergeSort(left)
MergeSort(right)
Merge(left, right, A)
}
No comments:
Post a Comment