이진탐색 - Binary Search

2022. 1. 2. 17:23

https://blog.naver.com/nagne2011/222610986947

1. 이진탐색 - Binary Search

 

 

#binarySearch #이진탐색

 

여담.

코딩 문제풀이 사이트 하나 추천합니다

https://leetcode.com/

이미지 썸네일 삭제

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

공부겸 진행하다가 기록을 남겨보려고 포스팅

 

 

 

첫번째 문제.

아래 내용을 구현하시오

대표사진 삭제

사진 설명을 입력하세요.

사진 삭제

사진 설명을 입력하세요.

public class Solution {
    public int Search(int[] nums, int target) {
        int index = -1;
        for(int i=0; i<nums.Length; i++)
        {
            if(nums[i] == target)
                index = i;
        }        
        return index;
    }
}

 

사진 삭제

사진 설명을 입력하세요.

대표사진 삭제

사진 설명을 입력하세요.

 

배열이 오름차순(혹은 내림차순)으로 정렬되어있을때

굳이 위 코드처럼 for문 돌려가며 하나씩 찾을 필요가 없다

 

이럴때 사용하는게 바로 이진탐색

 

예시를 보면 이해하기 더 쉽다

대표사진 삭제

사진 설명을 입력하세요.

시작점, 끝점을 각각 0과, 끝으로 두고

그 중간점을 찍고 결과기대값과 크다 작다를 비교해서 그 범위를 좁혀다가는 방식이다

 

위 gif를 보면 알듯 최소한의 움직임으로 원하는 대상을 찾을수있다

 

다만 크기값으로 비교해서 탐색하는 방식이라서

배열이 오름차순 혹은 내림차순으로 '소팅'되어야 사용할 수 있다는 점

 

    public int Search(int[] nums, int target) {
        int low = 0;
        int high = nums.Length - 1;
        
        while(low <= high)
        {
            int mid = low + ((high - low) / 2);
            
            if(target == nums[mid])
                return mid;
            else if(target < nums[mid])
                high = mid - 1;
            else 
                low = mid + 1;
        }       
        
        return -1;
    }

 

코드로 쓰면 이런느낌이다