이진 탐색

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

• 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다.
• 최악의 경우 시간 복잡도 O(N)

---

이진 탐색

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능하다.
• 시작점, 끝점, 중간점 의 위치를 나타내는 변수 3개를 사용한다.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
• 한 번 확인할 때마다 확인하는 원소의 개수가 반으로 줄어든다

• 시간 복잡도 O(logN)

탐색 과정

데이터가 이미 정렬이 되어있어야 한다

1. 시작점, 끝점을 확인한 다음 중간점을 정한다

• 중간점이 실수일 경우 소수점 이하를 버린다
  

2. 찾으려는 데이터와 중간점의 데이터를 비교한다
   1. 찾으려는 데이터 : 12 중간점의 데이터 : 8
   2. 찾으려는 데이터가 중간점보다 크기 인덱스 3이하는 더이상 확인할 필요가 없다 (이미 정렬되어 있는 데이터니까!)
   3. 따라서 시작점을 [4]로 변경한다.
   - 중간점은 (4+7)/2 = 5 (소수점 버림)
   

3. 중간점에 위치한 데이터 12는 찾으려는 데이터 12와 동일하므로 이 시점에서 탐색을 종료한다.

구현 방법

데이터가 이미 정렬되어 있어야 한다. 정렬이 되어있지 않으면
Arrays.sort(arr)로 정렬 후에 진행해 주자.

1. 재귀 함수를 이용하는 방법

	private static int binarySearch(int[] arr, int key, int start, int end) {
                //못찾음
		if(start>end) return -1; 
		int mid = (start + end)/2;
       	        //찾으면 인덱스 반환
		if(arr[mid]==key) return mid;
		//중간보다 크면, 중간 뒤 구간에서 다시 찾음
		else if(arr[mid]<key) return binarySearch(arr, key, mid+1, end);
		//중간보다 작으면, 중간 앞 구간에서 다시 찾음
		else return binarySearch(arr, key, start, mid-1);	
	}

2. 반복분을 이용하는 방법

	private static int binarySearch(int[] arr, int key) {
		int start = 0, end = arr.length-1;		
		//크기가 1보다 작으면 안됨(start==end면 1개, 교차되면 없어짐)
		while(start<=end) {
			int mid = (start + end)/2;
			if(arr[mid]==key) return mid; //인덱스 반환
			else if(arr[mid]<key) start = mid+1;
			else end= mid-1;
		}
		return -1;
	}
	

---

Arrays.binarySearch

JAVA에서는 Arrays.binarySearch(배열, 찾는 값)으로 편하게 사용할 수 있다.

Arrays.binarySearch는 int를 반환하는데

• 해당 값을 찾았을 경우 index를 반환한다
• 찾지 못했을 경우 ' -insertion point -1'을 반환한다.
  == 배열에 추가된다면 위치할 자리*(-1) -1
  == 만약 배열에 있었다면 위치했었을 자리*(-1) - 1

  [참고] 값에 1을 빼는 이유는 만약 반환 값이 0일 경우 +0과 -0의 구분을 할 수 없어서이다. 즉 값을 찾아서 0번째 인덱스에 존재한다는 의미vs값이 없고 만약 추가된다면 0번째 인덱스에 추가된다는 의미를 구분하기 위해서이다. 이처럼 -1을 해주면 무조건 값을 찾았을 경우에는 양수를 값을 찾지 못했을 경우에는 음수를 반환하게 된다.