찾기---2분 찾기의 세 가지 실현과 삽입값 찾기

이분 찾기

귀속 실현

구간은 좌폐우폐

구간은 좌폐우개

public class BinarySearchTest {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        int index1 = binarySearch1(arr, 5);
        System.out.println(index1);

        int index2 = binarySearch2(arr, 5);
        System.out.println(index2);

        int index3 = binarySearchRecursion(arr, 5);
        System.out.println(index3);
    }

    // 
    public static int binarySearchRecursion(int[] arr, int target) {
        return binarySearch3(arr, 0, arr.length - 1, target);
    }

    public static int binarySearch3(int[] arr, int left, int right, int target) {
        if(left > right) return -1;

        int mid = left + (right - left) / 2;

        if(arr[mid] > target) {
            return binarySearch3(arr, left, mid - 1, target);
        }else if(arr[mid] < target) {
            return binarySearch3(arr, mid + 1, right, target);
        }else {
            return mid;
        }
    }

    // ： 
    public static int binarySearch1(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }

    // ： 
    public static int binarySearch2(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while(left < right) {
            int mid = left + (right - left) / 2;
            if(target < arr[mid]) {
                right = mid;
            }else if(target > arr[mid]) {
                left = mid + 1;
            }else{
                return mid;
            }
        }

        return -1;
    }
}

확장 문제

그룹에 같은 목표 값이 여러 개 있습니다. 이 값의 아래 표시를 찾아내십시오. 예를 들어 {1,2,2,3,4} 목표 값이 2이면 {1,2}로 돌아갑니다.

import java.util.ArrayList;
import java.util.List;

public class BinarySearchExtension {
    public static void main(String[] args) {
        int[] arr = {1,2,2,3,4,4,4};
        List<Integer> result = binarySearchRecursion(arr, 3);
        System.out.println(result);
    }
    
    public static List binarySearchRecursion(int[] arr, int target) {
        return binarySearch1(arr, 0, arr.length - 1, target);
    }

    public static List binarySearch1(int[] arr, int left, int right, int target) {
        if(left > right) {
            return new ArrayList<>();
        }

        int mid = left + (right - left) / 2;
        if(arr[mid] > target) {
            return binarySearch1(arr, left, mid - 1, target);
        }else if(arr[mid] < target) {
            return binarySearch1(arr, mid + 1, right, target);
        }else{
            int temp1 = mid - 1;
            int temp2 = mid + 1;
            int arrLen = arr.length;
            List<Integer> result = new ArrayList<>();
            // mid 
            while(temp1 >= 0 && arr[temp1] == target) {
                result.add(temp1);
                temp1--;
            }
            result.add(mid);
            // mid 
            while(temp2 < arrLen && arr[temp2] == target) {
                result.add(temp2);
                temp2++;
            }
            return result;
        }
    }
}

시간 복잡도

매번 찾을 때마다 원소의 개수를 반으로 줄인다. 즉, n, n/2, n/4,..., n/2^k, k는 순환하는 횟수이다. n/2^k=1, 즉 k=logn(2를 밑으로), 따라서 시간의 복잡도는 O(logN)이다.

보간 찾기

2분 찾기에서 중간 원소mid= left + （right - left）/ 2를 추출하고 이런 예를 생각해 보자. 데이터는 1부터 1000까지이고 원소1을 찾으면 몇 번의 순환을 거쳐야 1을 찾을 수 있다.그래서 개선된 알고리즘은 바로 삽입 알고리즘이다. mid=left + (right - left) * (target -arr[left]) / (arr[right] - arr[left]), target은 목표 값을 찾아야 한다.데이터의 양이 비교적 크고 키워드의 분포가 비교적 균일한 검색에 있어 삽입값으로 찾는 속도가 비교적 빠르다.키워드의 분포가 고르지 않은 상황에서 이 방법이 반드시 2점보다 검색 효율이 높은 것은 아니다.