Leetcode 704) Binary Search

07 Sep 2021 in Algorithms

내 답안

• 새로운 함수를 만들어서 parameter로 어레이, start, end ind 계속 전달해주면서…
• 이렇게 할 필요없이, 포인터 두개로 해결 가능. 다른 답안 확인!

class Solution {
    public int search(int[] nums, int target) {
        return bs(nums,0,nums.length,target);
    }
    public int bs(int[] nums, int start, int end, int target){
        int mid = (start+end)/2;
        if(start == end){
            return -1;
        }
        
        if(nums[mid]==target){
            return mid;
        }
        
        //index는 모두 -1보다 크니까... , 그리고 mid는 제외한다. 아니니까..
        int res = Math.max(bs(nums,start,mid,target),bs(nums,mid+1,end,target));                
        return res;
    }
}

다른 답안

class Solution {
    public int search(int[] nums, int target) {
        //처음 들어온 어레이가 empty면 -1 리턴
        if(nums.length == 0) return -1;

        int left = 0;
        int right = nums.length - 1;

        left 가 right보다 작거나 같을 때 실행, target 과 mid와의 관계에 따라 left나 right를 옮겨준다.
        while(left <= right){
            int mid = left + (right - left) /2; //(left+right)/2 와 같다.

            if(nums[mid] == target){
                return mid;
            }

            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }

        return -1;        
    }
}