Array searching is the process of looking for a specific element or value within an array. There are many different algorithms that can be used to search an array, and the choice of which one to use can depend on the size of the array, the type of elements it contains, and the desired performance characteristics. Some common array search algorithms include linear search and binary search.

Linear Search

Linear search is a simple search algorithm that involves looking at each element of the array one by one, starting at the first element, until the desired element is found. This can be done by looping through the array and comparing each element to the search key until a match is found.

Here is an example of a linear search algorithm written in JavaScript:

function linearSearch(array, searchKey) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === searchKey) {
      return i // search key found, return its index
    }
  }
  return -1 // search key not found
}

// Example usage
const array = [8, 5, 3, 9, 1]
const searchKey = 5
const index = linearSearch(array, searchKey)

if (index >= 0) {
  console.log(`${searchKey} found at index ${index}`)
} else {
  console.log(`${searchKey} not found in array`)
}
//Output : 5 found at index 1

Linear search has a time complexity of O(n), where n is the size of the array. This means that the time taken by the algorithm increases linearly with the size of the array.

Binary Search

Binary search is a more efficient search algorithm that involves dividing the array in half and comparing the search key to the middle element. If the search key is less than the middle element, then the algorithm repeats the process on the left half of the array. If the search key is greater than the middle element, then the algorithm repeats the process on the right half of the array. This process is repeated until the search key is found or it is determined that the search key is not present in the array.

Here is an example of a binary search algorithm written in JavaScript:

function binarySearch(array, searchKey) {
  let left = 0
  let right = array.length - 1

  while (left <= right) {
    const middle = Math.floor((left + right) / 2)
    if (array[middle] === searchKey) {
      return middle // search key found, return its index
    } else if (array[middle] < searchKey) {
      left = middle + 1 // search in right half of array
    } else {
      right = middle - 1 // search in left half of array
    }
  }

  return -1 // search key not found
}

// Example usage
const array = [1, 3, 5, 8, 9]
const searchKey = 5
const index = binarySearch(array, searchKey)

if (index >= 0) {
  console.log(`${searchKey} found at index ${index}`)
} else {
  console.log(`${searchKey} not found in array`)
}
//Output : 5 found at index 1

This function takes an array and a search key as input, and returns the index of the first occurrence of the search key in the array, or -1 if the search key is not found. The function uses a while loop to repeatedly divide the search area in half until the search key is found or it is determined that the search key is not present in the array. The left and right variables keep track of the bounds of the search area, and the middle variable is calculated as the average of left and right. The value of the element at the index middle is compared to the search key, and the search area is updated accordingly. If a match is found, the index of the element is returned. If the search area becomes empty (left > right), the function returns -1, indicating that the search key was not found.

It’s important to note that this implementation of binary search only works on sorted arrays. If the array is not sorted, the results of the search will be unpredictable.

Binary search has a time complexity of O(log n), which means that the time taken by the algorithm increases logarithmically with the size of the array.

Conclusion

In general, binary search is much faster than linear search for large arrays. However, it can only be used if the array is already sorted, and it requires more memory to store the sorted array. Linear search, on the other hand, can be used with unsorted arrays and requires less memory. Therefore, the choice between linear search and binary search depends on the specific requirements of the problem you are trying to solve.