Searching and Sorting

CSL 102; Data Structures; IIIT Nagpur; Created by: Dr. Aniket Pingley

Linear search

Linear search or sequential search is a method for finding an element within a array. Starting with the value of zero-eth index, linear search mechanism sequentially checks each element of the array until a match is found or the whole array has been searched. For an array of size n, linear searching requires n comparisons in the worst case. The example below makes it amply clear. The target value, or the value to be searched, in this example is 8.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 11 (skipping steps 6 through 10):

A more detailed animation can be found HERE.

Generalized algorithm

Consider an array A of n elements with values or records A0 .... An−1, and target value L, the following algorithm performs linear search to find the index of the target L in A. Let i be the index.

1. i = 0;
2. If Ai == L { return i; }, the search terminates successfully.
3. i++;
4. If i < n, go to step 2.
5. If i == n, the search terminates unsuccessfully.

  int linearSearch(int arr[], int sz, int key){
    int index = -1;
    for(int idx = 0; idx < sz; idx++){
        if (key == arr[idx]){
            index = idx;
            break;
        }
    }
    return index;
  }
  

Binary Search

Unlike the linear search algorithm above, binary search can only be performed on arrays that are sorted (typically ascending order). This technique capitalizes on the mathematical relationship (sorted) of values located at contiguous locations. Binary search works by repeatedly dividing in half the portion of the array that could contain the target value, until the possible locations are narrowed down to just one. In this example, the target value is 82.

Step 1:

Step 2:

Step 3:

Step 4:

A more detailed animation can be found HERE.

Generalized algorithm

Consider an array A of n elements with values or records A0 .... An−1, and target value T, the following algorithm performs binary search to find the index of the target T in A. Let i be the index. It must be noted that A is already sorted such that A0 ≤ A1 ≤ A2 ≤ A3 ≤ ⋅⋅⋅ ≤ An, i.e. sorted in ascending order.

1. Set low to 0 and high to n-1
2. If low > high, the search is terminated
3. Set mid be the floor value of (low + high)/2
4. If Amid is < T, set low = mid+1. Go to Step 2.
5. If Amid is > T, set high = mid-1. Go to Step 2.
6. If Amid == T, return mid. Terminate the search.

  int binarySearch(int arr[], int sz, int key){
    int index = -1;
    int left = 0, right = sz - 1, mid = 0;
    while(left <= right){
        mid = (left + right)/2;
        if (key == arr[mid]){
            index = mid;
            break;
        }
        if(arr[mid] < key){
            left = mid+1;
        }
        else{
            /*if(arr[mid] > key){}*/
            right = mid-1;
        }
    }
    return index;
  }