Java 클래식 알고리즘 이진 검색의 원리 및 구현 그림

이 기사에서는 java에 대한 관련 지식을 제공합니다. 절반 검색 방법은 이름에서 알 수 있듯이 데이터를 두 부분으로 나눈 다음 어느 절반에서 키가 발견되었는지 확인한 다음 위의 작업을 반복합니다. 이제 대상 키를 찾았으니 모두에게 도움이 되기를 바랍니다.

추천 학습: "java 동영상 튜토리얼"

이진 검색

이진 검색은 이진 검색(Binary Search)이라고도 하며 데이터의 로그에 사용할 수 있는 보다 효율적인 검색 방법입니다. 시간복잡도 내에서 검색을 완료하세요. 정렬된 배열에서 특정 요소를 찾는 검색 알고리즘입니다.

알고리즘 아이디어

오름차순 시퀀스를 예로 들어 대상 요소와 시퀀스 중간에 있는 요소의 크기를 비교하고 대상 요소가 중간에 있는 요소보다 크면 이진 검색을 계속 수행합니다. 시퀀스의 후반부에서 대상 요소가 중간 위치의 요소보다 작으면 배열의 전반부에서 비교가 이루어지며, 요소의 위치가 검색됩니다. 각 비교에 대한 배열의 길이는 동일한 요소의 위치를 ​​찾거나 대상 요소를 찾을 수 없을 때까지 이전 배열의 절반이 됩니다.

Illustration

오름차순으로 정렬된 배열이 주어지면 nums=[-1, 0, 2, 5, 8, 12, 18, 38, 43, 46]

그런 다음 배열 =12에서 대상 값 target을 찾습니다.

다이어그램은 다음과 같습니다.

원래 질문에 가깝습니다

Portal

문제 설명:

n개 요소로 정렬된(오름차순) 정수 배열 num과 대상 값 대상이 주어지면 함수 검색을 작성합니다. 숫자 단위의 대상에 대해 대상 값이 존재하면 아래 첨자를 반환하고, 그렇지 않으면 -1을 반환합니다.

예 1:

입력: nums = [-1,0,3,5,9,12], target = 9
출력: 4
설명: 9는 nums에 나타나고 아래 첨자는 4

예 2:

입력: nums = [-1,0,3,5,9,12], target = 2
출력: -1
설명: 2는 nums에 존재하지 않으므로 -1이 반환됩니다

문제 해결 아이디어:

질문의 의미에 따르면 배열은 순서 배열이라는 결론을 내릴 수 있으며 이는 이진 검색을 사용하기 위한 전제 조건이기도 합니다.

• 배열의 첫 번째 요소와 마지막 요소를 각각 가리키는 두 개의 포인터를 정의합니다.
• 배열의 중간 값을 찾습니다.
• nums[mid] < 배열 부분의 후반부에 위치합니다. 그렇지 않으면 <code>nums[mid] > target이 전반부에 있습니다. nums[mid] < target，则 target 位于数组的后半部分，反之nums[mid] > target在前半部分；
• 重复上一步操作，直到nums[mid] = target
nums[mid] = target이 될 때까지 이전 단계를 반복합니다. code>, 대상을 찾았고 아래 첨자가 반환되었음을 나타냅니다. 그게 다입니다.

Java 코드 구현:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right) { // 循环条件
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 找不到则返回-1
    }
}

복잡도 분석:

• 시간 복잡도: O(logn), 여기서 n은 배열의 길이입니다.
• 공간 복잡도: O(1).

추천 학습: "java 비디오 튜토리얼

"🎜

위 내용은 Java 클래식 알고리즘 이진 검색의 원리 및 구현 그림의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!