배열 - 2 분 찾기

1. LintCode 링크
http://www.lintcode.com/zh-cn/problem/first-position-of-target/
2. 문제 설명
정렬 된 정수 배열 (오름차 순) 과 찾 을 정수 target 을 지정 합 니 다. O (logn) 의 시간 으로 target 이 처음 나타 난 아래 표 시 를 찾 습 니 다 (0 부터). target 이 배열 에 존재 하지 않 으 면 - 1 로 돌아 갑 니 다.
3. 관건 적 인 분석
  • 오름차 배열
  • 데이터 양
  • n0 & lt; = n1 & gt; = n2 & gt; =.., 데이터 가 연속 으로 같 을 수 있 음
  • 처음 나타 난 하 표
  • 4. 해결 방향 (자바)
    1. 데이터 양 이 많 지 않 고 재 귀 법 과 비 재 귀 법
    귀속 법
     public int binarySearch(int[] nums, int fromIndex, int toIndex, int target) {
            if (nums == null || nums.length <= 0
                 || fromIndex > toIndex || fromIndex < 0 || toIndex >= nums.length) {
                return -1;
            }
    
            int midIndex = (fromIndex + toIndex) >>> 1;
            int midValue = nums[midIndex];
    
            if (midValue < target) {
                return binarySearch(nums, midIndex + 1, toIndex, target);
            } else if (midValue > target) {
                return binarySearch(nums, fromIndex, midIndex - 1, target);
            } else {
                int beforeIndex = binarySearch(nums, fromIndex, midIndex - 1, target);
                return beforeIndex > 0 ? beforeIndex : midIndex;
            }
        }
    

    비 귀속 법
     public int binarySearch(int[] nums, int target) {
            if (nums == null || nums.length <= 0) {
                return -1;
            }
    
            int resultIndex = -1;
    
            int fromIndex = 0;
            int toIndex = nums.length - 1;
    
            while (fromIndex <= toIndex) {
                int midIndex = (fromIndex + toIndex) >>> 1;
                int midValue = nums[midIndex];
    
                if (midValue < target) {
                    fromIndex = midIndex + 1;
                } else if (midValue > target) {
                    toIndex = midIndex - 1;
                } else {
                    resultIndex = midIndex;
                    toIndex = midIndex - 1;
                }
            }
            return resultIndex;
        }
    

    2. 데이터 양 이 많 으 면 트 리 나 더미 와 Quick Select 알고리즘 (TODO) 을 사용 합 니 다.
    관련
    1. 소스 코드 의 2 분 찾기
        SparseArray.get  :
        public E get(int key, E valueIfKeyNotFound) {
            int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
            if (i < 0 || mValues[i] == DELETED) {
                return valueIfKeyNotFound;
            } else {
                return (E) mValues[i];
            }
        }
    
        ContainerHelpers.binarySearch()  :
        static int binarySearch(int[] array, int size, int value) {
            int lo = 0;
            int hi = size - 1;
    
            while (lo <= hi) {
                final int mid = (lo + hi) >>> 1;
                final int midVal = array[mid];
    
                if (midVal < value) {
                    lo = mid + 1;
                } else if (midVal > value) {
                    hi = mid - 1;
                } else {
                    return mid;  // value found //              ,            
                }
            }
            return ~lo;  // value not present
        }
    

    2. 링크
    위 키. - 2 분 검색.

    좋은 웹페이지 즐겨찾기