코딩테스트 기초 배열 Binary Search | 코드없는 프로그래밍

출처 코드없는 프로그래밍

코딩테스트, 기초, 배열 인터뷰 바이너리 서치 - YouTube

 

array - binary search

배열이 정렬이 되어있는 상태에서 어떤 값을 찾아달라!

 

어떤 배열 [1,3,5,6,7,15,20]에서 15의 인덱스를 찾고자 한다면? 

<내 풀이>

#어떤 배열 [1,3,5,6,7,15,20]에서 15의 인덱스를 찾고자 한다면? 

def solution(s, a):
  index = 0
  search_index = 0
  while True:
    if a == s[search_index]:
      index = search_index
      break
    elif a < s[search_index]:
      search_index //= 2
    else:
      search_index += len(s)
      search_index //= 2    
  return index

s = [1,3,5,6,7,15,20]
print(solution(s,15))

 

 

Binary search를 사용하면 O(logn)의 시간복잡도로 해결할 수 있다.

idea

 

left

right

 

pivot = (L + R) / 2

pivot을 이용해서 left와 right의 위치를 업데이트한다. 

 

찾을 수 없으면 -1 retrun

 

def solution(s, a):
  left = 0
  right = len(s) - 1

  while True:
    pivot = (left + right) // 2 
    #print(pivot)
    if s[pivot] == a:
      return pivot
      break    
    if left > right or right < left:
      return -1
      break
    elif s[pivot] > a:
      right = pivot
    elif s[pivot] < a:
      if left == right - 1:
        left = pivot + 1
      else:
        left = pivot

예제

int search(int [] nums, int target)
{
  int left = 0;
  int right = nums.length - 1;

  while (left <= right)
  {
    int pivot = (left+right) /2
    if (nums[pivot]==target)
    {
      return pivot;
    }
    else if (nums[pivot]<target)
    {
      left = pivot + 1;
    }
    else
    {
      right = pivot - 1;
    }
  }
}

문제 - (1) Binary Search - LeetCode

Binary Search - LeetCode