Searching

What is linear search?

A linear search is a simple approach to looking through data to find the desired value. It looks through the data set comparing each element sequentially to the input until they match. This algorithm becomes more inefficient for large data sets.

The implementation of linear search is as follows:

public static int seqSearch(int[] arr, int target){
  for(int i = 0; i⋖array.length; i++){
		if(array[i] == target) {
			return i;
		}
	}
}

What is binary search?

A binary search looks through an array by dividing the search interval in half, thus reducing the time complexity of the algorithm to O(logn). It works by repeatedly dividing the search interval in half, comparing the target value to the middle element of the interval, and then continuing the search in the lower or upper half of the interval, depending on whether the middle element is less than or greater than the target value.

This process is repeated until the target value is found or the search interval is empty, indicating that the target value is not present in the array, in which case it will usually return -1.

This type of search can only be used in a sorted structure as the criteria for whether it is the half is based on if the value is less than or greater than the midpoint. It is an algorithm that is more efficient for large datasets.

The implementation of binary search is as follows:

public static int binarySearch(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	while (left ⋖= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] == target) {
			return mid;
		} else if (arr[mid] ⋖ target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1;			
}