Types of Searches

Sequential Search

Sequential search works by scanning the list, comparing each element to the target value until it is found. The average number of comparisons, assuming the target value is in the array, is n/2, where n is the array's length. The worst case is that the searching algorithm must check each element to find it, or to establish that the target value is not in the array.

Because of this, the sequential sort is a O(n) algorithm.

Binary Search

The binary search requires the array to be sorted in ascending/descending order to work. Therefore, we would have to use a sorting algorithm on an unsorted array before using the binary search algorithm.

The target value is compared with the middle element of the search range, which at the beginning is position 0-array.length - 1, but changes. It then compares the value of the element in the middle position with the target, and if it is greater than the target (assuming the array is sorted in ascending order), the end of the search range is now the middle position -1.

This is the same for if the target is greater, but we instead make the search range from the middle position + 1 to the end of the array. Binary search is therefore known as a divide and conquer algo, as it is very efficient in eliminating unneccesary regions of the array to search. For an array of 1,000,000 elements, only 20 comparisons are needed! Binary search is also considered a O(log n) algorithm.

As we can see above, the middle position is determined by averaging the lowest and highest position. This is done each time until the target is found, as the search range begins to become smaller and smaller.

Sorting

Sorting means to rearrange the elements of a list in ascending or descending order. Sorting algorithms that compare each element to one another usually take an average of n(n-1)/2 comparisons, where faster divide and conquer algorithms take nlog2n comparisons.

Insertion Sort

Insertion sort works by splitting the array into two subarrays, the sorted subarray located at the lower positions of the list, and the unsorted subarray which consits of the rest of the elements in the array. It is a O(n^2) sorting algorithm.

The next unsorted element is inserted into the sorted subarray by moving any larger values to the right. This is done for each element in the unsorted section, from index 1 through the entire array. The diagram below describes merge sort, step by step, for sorting an array of length 4.

Mergesort

Merge sort is a divide-and-conquer algorithm that works by breaking down an array into several sub-arrays until each subarray consists of a single element. This is done recursively by invoking a merge sort on both halves of the subarray.

Once each element now forms an array of size one, we merge these subarray's according to their value. This is done many times until one single sorted array is obtained.