이진 탐색 (Binary Search)

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 

 

https://www.geeksforgeeks.org/binary-search/

Binary Search - GeeksforGeeks

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

public class Solution6{
        public Solution6(){
            int[] arr = {1,2,3,7,9,12,21,23,27};
            //var index = this.BSearchRecur(arr, 0, arr.Length-1, 9);
            var index = this.BSearch(arr, 12);
            Console.WriteLine("index:{0}, value:{1}", index, arr[index]);
        }
 
        private int BSearchRecur(int[] arr, int start, int end, int target){
            int mid = (start + end) /2;
            if(start>end){
                return -1;
            }else{
                if(arr[mid] == target){
                    return mid;
                }else{
                    if(arr[mid] > target){
                        return this.BSearchRecur(arr, start, mid-1, target);
                    }else{
                        return this.BSearchRecur(arr, mid+1, end, target);
                    }
                }
            }
        }
 
        private int BSearch(int[] arr, int target){
            int start = 0;
            int end = arr.Length-1;
            int mid = 0;
 
            while(start<= end){
                mid = (start+end)/2;
                if(arr[mid] == target){
                    return mid;
                }else{
                    if(arr[mid] > target){
                        end = mid -1;
                    }else{
                        start = mid+1;
                    }
                }
            }
            return -1;
        }
    }