【九月打卡】第32天 数据结构和算法

顺序搜索

• 数组从头开始遍历，找出相应的元素下标，找不到返回-1
• 时间复杂度为O(n)，搜索效率低

function sequential(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(sequential([1, 2, 3, 4], 3))

二分搜索（有序数组）

注：二分搜索只适用于有序数组；如果是乱序数组，需要先排序再进行二分搜索

• 从数组的中间元素开始，如果中间元素等于目标元素，搜索结束
• 如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (target > arr[mid]) {
      start = mid + 1;
    } else if (target < arr[mid]) {
      end = mid - 1;
    } else {
      return mid
    }
  }
  return -1;
}

binarySearch([1, 2, 3, 4], 5)

时间复杂度：O(logn)