이진검색, 선형검색

탐색 알고리즘

• 검색의 다른 명칭이 탐색
• 데이터 탐색 프로그램에서 사용하고 있는 알고리즘
• 최대한 빠르게, 검색 작업을 수행하는 것
• 자매품으로 정렬알고리즘(sorting): 자료를 정리

선형검색(linear search)

• 왼쪽에서부터 순서대로 검색
• 탐색 시작 -> 결과를 찾을 때까지 루프 반복 -> 결과를 찾거나 루프가 끝나면 탐색 종료
• 최악의 경우: 찾으려는 값이 맨 마지막에 있거나 없는 경우
  
  
• 배열이 커지면 커질수록 검색시간이 길어짐
• 선형탐색의 시간복잡도: O(n)
  

//배열의 요소가 5인 인덱스 찾기
let findIndexLinear = (arr, num) => {
	for(let i=0; i<arr.length; i++) {
   		if(arr[i] === num) return i;
    }
  return `${num} not in Array.`
}

findIndexLinear([2,4,5,1,6], 6)
findIndexLinear([2,4,5,1,6], 10)

이진검색(binary search)

• 선형검색을 보완하기 위해 나온 알고리즘
• 이진검색은 정렬된 알고리즘에서만 검색 가능
• 탐색방법
  • 가운데에 있는 요소를 탐색
  • 가운데에 있는 요소보다 큰지 작은 비교하여 탐색범위를 정함
  • 그 정한 탐색범위에서 다시 한번 가운데 탐색
  • 계속 해서 찾을 때까지 반복하여 원하는 결과를 찾으면 탐색종료
    
• 이진 탐색의 시간복잡도: O(logN)
  
• 평균적으론 데이터가 많고 원하는 데이터가 끝부분에 있는 경우는 이진탐색이 빠름.

let findIndexBinary = (arr, num) => {
  let head = 0;
  let tail = arr.length - 1;
  let mid = Math.floor((head+tail)/2)
  
  while(arr[mid] !== num) {
    // 머리가 꼬리보단 긴 경우는 배열의 없는 숫자임.
    if(head>tail) return `${num} not in Array`;
    
    if(arr[mid] < num) {
      head = mid + 1;
      mid = Math.floor((head+tail)/2);
    } else {
      tail = mid - 1;
      mid = Math.floor((head+tail)/2);
    }
  }
  // 해당 숫자의 인덱스 리턴
  return mid
}

findIndexBinary([1,2,3,4,5,7], 4)

다음 탐색 알고리즘은 해쉬탐색법으로!

출처 - 노마드코더