Searching Algorithm

Linear Search

How do we search?

Given an array, the simplest way to search for a value is to look at every element in the array and check if it's the value we want.

if our array is not sorted, in this case the best way to search is to look at every element in the array. => That is called Linear Search

JavaScript has search!

There are many different search methods arrays in JavaScript:

1. indexOf
2. includes
3. find
4. findIndex

Big O of Linear Search

Best => O(1) Worst => O(n) Average => O(n)

Binary Search

Binary Search is a much faster from a search

Rather than eliminating one element at a time, you can eliminate half of the remaining elements at a time

Binary Search only works on sorted arrays => so the data has to be sorted to seach using Binary search

The idea is Divide and Conquer

Binary Search Pseuducode

• This function accepts a sorted array and a value
• Create a left pointer at the start of the array, and a right pointer at the end of the array
• While the left pointer comes before the right pointer:

1. Create a pointer in the middle
2. if you find the value you want, return the index
3. if the value is too small, move the left pointer up
4. if the value is too large, move the right pointer down
5. If you never find the value return -1.

function binarySearch(arr, value) {
  let start = 0;
  let end = arr.length -1;
  let middle = Math.floor((start + end) / 2);

  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) end = middle - 1; 
    else start = middle + 1;
    middle = Math.floor((start + end) / 2);
  }

  return arr[middle] === value ? middle : -1;
}

binarySearch([2, 5, 6, 9, 13, 15, 28], 15)

Big O of Binary Search

Worst and average case => O(log n)

Best case => O(1) Worst and Average case => O(log n)

Naive String Search

search for substrings in a larger string.

Suppose you want to count the number of times a smaller string appears in a longer string.

for example I wanna search for haha in the string harold said haha in hamburg

• 1. Loop over the longer string
• 2. Loop over the shorter string
• 3. If the characters don't match, break out the inner loop
• 4. If the characters do match, keep going
• 5. If you complete the inner loop and find a match, increment the count of matches
• 6. Return the count

function naiveSearch(long, short) {
  for(let i = 0; i < long.length; i++) {
    for(let j = 0; j < short.length; j++) {
      short[j] !== long[i+j]
    }
  }
}

naiveSearch("lorie loled", "lol")