Lecture Notes 5.pdf

COMP1210 - Lecture Notes 5 Introduction Searching Algorithms Linear Search Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found. Note the arr...

COMP1210 - Lecture Notes 5 Introduction Searching Algorithms Linear Search Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found. Note the array does not have to be sorted for this search to work. Following are the steps of implementation that we will be following: 1. Traverse the array using a for loop. 2. In every iteration, compare the target value with the current value of the array. o If the values match, return the current index of the array. o If the values do not match, move on to the next array element. 3. If no match is found, return -1. Sample Code: int linearSearch(int values[], int target, int n) { for (int i = 0; i < n; i++) { if (values[i] == target) { return i; } } return -1; } Binary Search  Binary search works only on sorted arrays  Binary search begins by comparing an element in the middle of the array with the target value.  If the target value matches the element, its position in the array is returned.  If the target value is less than the element, the search continues in the lower half of the array.  If the target value is greater than the element, the search continues in the upper half of the array.   By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration. Left half Right half Arr[] 1 3 4 6 7 10 13 14 18 19 21 24 37 40 45 71 74 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 start finish target = 40 Get middle index mid = (start+finish)/2 = (0+16)/2 = 8 if Arr[mid] == target then stop cause you have found what you were looking for If target is greater than the value at the middle index , then what we are looking for is in the right half, focus only on that side or if target is less than value a middle index focus on the left half Left half Right half Arr[] 18 19 21 24 37 40 45 71 74 8 9 10 11 12 13 14 15 16 start finish Get middle index mid = (finish+start)/2 = (8+16)/2 = 12 if Arr[mid] == target then stop cause you have found what you were looking for If target is greater than the value at the middle index , then what we are looking for is in the right half, focus only on that side or if target is less than value a middle index focus on the left half Left half Right half Arr[] 37 40 45 71 74 12 13 14 15 16 start finish Get middle index mid = (start+finish)/2 = (12+16)/2 = 14 if Arr[mid] == target then stop cause you have found what you were looking for If target is greater than the value at the middle index , then what we are looking for is in the right half, focus only on that side or if target is less than value a middle index focus on the left half Left Right Arr[] 37 40 45 12 13 14 start finish Get middle index mid = (start+finish)/2 = (12+14)/2 = 13 if Arr[mid] == target then stop cause you have found what you were looking for Index storing the target is found at this point Sample code: #include using namespace std; int binarySearch(int Arr[], int target, int start, int finish) { // termination condition (element isn't present) while (start Arr[mid]) start = mid + 1; // if target is smaller than the middle element // finish gets mid-1, taking the right half out of consideration else if (target < Arr[mid]) finish = mid - 1; } return -1; } int main() { int Arr[] = { 1,2,4,6,7,10,13,14,18,19,21,24,37,40,45,71,74 }; int target = 40; // value being search for  int start = 0; int finish = (sizeof(Arr) / sizeof(Arr)) - 1; int result = binarySearch(Arr, target, start, finish); if (result == -1) cout A[m]), then jump to the next block.  Iteration 3: if (x==A[2m]), then success, else, if (x > A[2m]), then jump to the next block.  At any point in time, if (x < A[km]), then a linear search is performed from index A[(k- 1)m] to A[km] It has been shown that the optimal size of m is √n. Therefore if n = 16, then m would be 4 (Block size). m 2m 3m 1 3 4 6 7 10 13 14 18 19 21 24 37 40 45 71 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Steps for Jump Search Algorithms: Array name is A and search value is item Step 1: Set i=0 and m = √n. Step 2: Compare A[i] with item. If A[i] != item and A[i] < item, then jump to the next block. Also, do the following: 1. Set i = m 2. Increment m by √n Step 3: Repeat the step 2 while m < n-1 Step 4: If A[i] > item, then move to the beginning of the current block and perform a linear search. 1. Set x = i 2. Compare A[x] with item. If A[x]== item, then print x as the valid location else set x++ 3. Repeat Step 4.1 and 4.2 while x < m Step 5: Exit Pictorial Representation of Jump Search with an Example Let us trace the above algorithm using an example: Consider the following inputs:  A[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}  item = 77 Step 1: m = √n = 4 (Block Size) Step 2: Compare A with item. Since A != item and A