이분 찾기 - LintCode

정렬 된 정수 배열 (오름차 순) 과 찾 을 정수 target 를 지정 하고 O(logn) 의 시간 으로 target 이 처음 나타 난 아래 표 시 를 찾 습 니 다 (0 부터). target 이 배열 에 존재 하지 않 으 면 되 돌아 갑 니 다 -1.
당신 은 실제 면접 에서 이 문 제 를 만난 적 이 있 습 니까? 
Yes
본보기
배열  [1, 2, 3, 3, 4, 5, 10]  중 2 점 찾기 3, 복귀 2.
도전 하 다.
만약 배열 의 정수 개수 가 2 ^ 32 를 초과 한다 면, 당신 의 알고리즘 은 오류 가 발생 할 수 있 습 니까?
**********************************
2 점 에서 찾 았 는데 2 점 에서 찾 았 습 니 다. 처음 나타 난 자 리 를 찾다
배열 의 정수 개수 가 2 ^ 32 회 를 초과 하면... 문제 가 있 을 수 있 습 니 다. nums. length 의 반환 값 은 int 입 니 다. 그러면 문제 가 생 겨 요.
class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        int low = 0;
		int high = nums.length-1;
		int a = -1;
		while(low <= high)
		{
			int mid = (low + high)/2;
			if(target > nums[mid]){
				low = mid +1;
			}
			else if (target == nums[mid]) {
				a = mid;
				high = mid-1;
			}
			else {
				high = mid -1;
			}
		}
		if(a != -1)
		{
			return a;
		}
		return -1;
    }
}

좋은 웹페이지 즐겨찾기