이진 검색 알고리즘(binary search algorithm)

이진 검색 알고리즘 : 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘.

전체 배열에서 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 배열을 순차적으로 검색하는 선형검색보다  속도가 빠르다는 장점이 있다.

작은 크기의 정렬된 배열이라면 이진검색이나 선형검색이나 비슷한 시간을 소요하지만

100개의 값을 가지고 있는 배열에서 최대 단계수는 선형검색은 100단계를 이진검색은 7단계정도만을 거치면 된다.

이진 검색 알고리즘은 주어진 배열이 정렬되어 있다고 가정하고 동작한다. 따라서 검색하려는 값이 배열에 없으면 검색 범위를 좁혀가면서 계속해서 반으로 쪼개나가다가 결국에는 검색 범위가 더 이상 없어지게되면 null반환하고 찾는 값이 배열에 없다고 알려준다.

 

#누구나자료구조와알고리즘

책에 나온 루비로직>

def binary_search(array, search_value)
  lower_bound = 0
  upper_bound = array.length - 1

  while lower_bound <= upper_bound do
    midpoint = (upper_bound + lower_bound) / 2
    value_at_midpoint = array[midpoint]

    if search_value == value_at_midpoint
      return midpoint
    elsif search_value < value_at_midpoint
      upper_bound = midpoint - 1
    elsif search_value > value_at_midpoint
      lower_bound = midpoint + 1
    end
  end

  return nil
end

p binary_search([3, 17, 75, 80, 202], 22)

자바 로직>

package algorithm;

public class BinarysearchAlgorithm {

	public static Integer BinarySearch(int[]array, int searchValue) {
		
		int lower = 0; //배열의 가장 작은 인덱스를 나타내며 초기값은 0
		int upper = array.length - 1;
		//배열의 가장 큰 인덱스를 나타내며 초기값은 array.length - 1
		
		while(lower <= upper) { // lower가 upper보다 작거나 같은동안 계속 반복
			int midPoint = (upper + lower) /2;
			int valueAtMidpoint = array[midPoint]; 
			// 범위내 중간 지점에 있는 항목
			
			if(searchValue == valueAtMidpoint) {
				return midPoint;
				// valueAtMidpoint가 찾는 값이 searchValue 이면 성공이고, 그 인덱스 값 반환가능
			} else if(searchValue < valueAtMidpoint) {
				upper = midPoint -1;
				// valueAtMidpoint가 searchValue보다 크다면 searchValue를 앞 부분에서만 찾겠다
				// 이제 upper에 midPoint는 왼쪽 인덱스를 할당해 검색 범위를 좁히는 것이다.
			} else if(searchValue > valueAtMidpoint) {
				lower = midPoint + 1;
				// 반대로 searchValue가 크면 searchValue를 midPoint 오른쪽 값들에게서만 찾겠다
			}
		}
		
		return null;
	}
	
	public static void main(String[] args) {
		int[] array = {3,17,75,80,202};
		int searchValue = 22;
		
		System.out.println(BinarySearch(array, searchValue));
	}
}

-> 22는 찾는 배열에 없음으로 null이 출력된다.

 

 

C#로직

using System;

class BinarySearch
{
    static int? BinarySearchMethod(int[] array, int searchValue)
    {
        int lowerBound = 0;
        int upperBound = array.Length - 1;

        while (lowerBound <= upperBound)
        {
            int midpoint = (upperBound + lowerBound) / 2;
            int valueAtMidpoint = array[midpoint];

            if (searchValue == valueAtMidpoint)
            {
                return midpoint;
            }
            else if (searchValue < valueAtMidpoint)
            {
                upperBound = midpoint - 1;
            }
            else if (searchValue > valueAtMidpoint)
            {
                lowerBound = midpoint + 1;
            }
        }

        return null;
    }

    static void Main()
    {
        int[] array = { 3, 17, 75, 80, 202 };
        int searchValue = 22;

        Console.WriteLine(BinarySearchMethod(array, searchValue));
    }
}