LeetCoding Challenge Oct. 8: Binary Search

4129 단어 JavaLeetCodetech
LetCode October Charling 8일차.
오늘의 문제는Binary Search입니다.

문제의 개요

  • 2분 검색 실현
  • 요소를 찾으면 색인을 되돌려주고 그렇지 않으면 -1
  • 을 되돌려줍니다.

    생각


  • 그저께, 이어서 어제/어제(약)
  • 단순한 이분탐색을 경시하지 말고 실수 없이 이룬 의외의 어려움...
  • 특히 문제가 발생하기 쉬운 것은 구간 중앙에서 색인을 구하는 처리에서 넘침을 피해야 한다는 것이다(이번 문제라면 요소의 수량이 최대 10000이므로 넘침에 신경 쓸 필요가 없다...)
  • 자바는 논리적 오른쪽 위치 이동 계산자>>>가 있기 때문에 이걸로 넘침을 두려워하지 않습니다!
  • 이후 구간의 오른쪽이include인지 exclude인지 주의하면 됩니다
  • 다음 코드submit으로runtime 0ms에 도달👍
  • 코드


    class Solution {
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (nums[mid] == target) {
                    return mid;
                }
    
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {  // nums[mid] > target
                    right = mid - 1;
                }
            }
            return -1;
        }
    }
    

    좋은 웹페이지 즐겨찾기