Java에서 이진 검색을 구현하는 방법은 무엇입니까?-java지도 시간-php.cn

Java에서 이진 검색을 구현하는 방법은 무엇입니까?

藏色散人

풀어 주다： 2019-03-19 13:38:12

원래의

4135명이 탐색했습니다.

Java에서 이진 검색을 수행하는 방법에는 두 가지가 있습니다.

Java에서 이진 검색을 구현하는 방법은 무엇입니까?

1.Arrays.binarysearch()는 기본 데이터 유형일 수도 있는 배열에서 작동합니다.

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

로그인 후 복사

출력:

22 found at index = 3
40 Not found

로그인 후 복사

2.Collections.binarysearch()ArrayList 및 LinkedList와 같은 개체 컬렉션에 적용됩니다.

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

로그인 후 복사

출력:

10 found at index = 3
15 Not found

로그인 후 복사

입력이 정렬되지 않으면 어떻게 되나요?
입력 목록이 정렬되어 있지 않으면 결과가 정의되지 않습니다.

중복이 있으면 어떻게 해야 하나요?
중복된 항목이 있는 경우 어떤 항목이 발견되는지 보장할 수 없습니다.

LinkedList에서 Collections.binarySearch는 어떻게 작동하나요?
이 방법은 log(n) 시간에 실행되며 ArrayList와 같은 "임의 액세스" 목록에 사용됩니다. 지정된 목록이 RandomAccess 인터페이스를 구현하지 않고 큰 경우 이 메서드는 O(n) 링크 순회 및 O(log n) 요소 비교를 수행하는 반복자 기반 이진 검색을 수행합니다.

두 함수가 반환하는 음수 값의 의미는 무엇인가요?
이 함수는 검색 키의 인덱스를 반환합니다(배열에 포함된 경우). 그렇지 않으면 (-(삽입 지점)-1). 삽입 지점은 키가 배열에 삽입되는 지점으로 정의됩니다. 첫 번째 요소의 인덱스는 키보다 크거나, 배열의 모든 요소가 지정된 키보다 작은 경우 a.length입니다. 이는 키가 발견된 경우에만 반환 값 >= 0을 보장한다는 점에 유의하세요.

Java에서 자체 이진 검색을 구현하는 방법은 무엇입니까?

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = {2,3,4,10,40}; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr,0,n-1,x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " +  
                                                 result); 
    } 
}

로그인 후 복사

출력:

Element found at index 3

로그인 후 복사