[Leetcode] Algorithm Day1 Binary Search

Binary Search

Binary Search(이진 탐색)

이진 탐색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

최소값는 리스트의 첫 번째 값이고, 최대값은 리스트의 마지막으로 설정한다.

중간의 값을 중앙값으로 설정하고, 중앙값 < target 이면 중앙값은 찾고자 하는 값의 새로운 최소값이 되고, 중앙값 > target이면 중앙값이 새로운 최대값이 된다. 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두배가 되므로 속도의 측면에서는 장점이다.

 

704. Binary Search

기본적인 binary search이다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let answer = -1;
  let start = 0;
  let last = nums.length - 1;
  while (start <= last) {
    let mid = parseInt((start + last) / 2);
    if (nums[mid] === target) {
      answer = mid;
      break;
    } else if (nums[mid] > target) {
      last = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return answer;
};

 

278. First Bad Version 

이미 isBadVersion()이라는 함수가 리트코드 내에서 정의되어 있고 그것을 사용하는 것이다.

mid가 true이면 그 값을 answer로 일단 넣어두고 그보다 작은 isBadVersion(mid) === true인 값이 있으면 answer을 재할당한다.

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let answer = 0
        let first = 1
        let last = n
        while(first<=last){
            let mid = parseInt((first+last)/2);
            if(isBadVersion(mid)){
                last = mid-1
                answer = mid
            }else{
                first = mid+1
            }
        }
        return answer
    };
};

35. Search Insert Position

answer에 mid보다 하나 큰 index값을 저장한다

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let answer = 0;
  let first = 0;
  let last = nums.length - 1;
  while (first <= last) {
    let mid = parseInt((first + last) / 2);
    if (nums[mid] < target) {
      answer = mid + 1;
      first = mid + 1;
    } else {
      last = mid - 1;
    }
  }
  return answer;
};

 

 

참고

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전