2019-03-11 TIL

코드잇 ) 프로그래밍 기초

정렬

• 삽입 정렬 - 0번 인덱스부터 시작해서 하나씩 각 값의 자리를 찾아주는 알고리즘 ❌
• 합병 정렬 ❌

알고리즘

• Logarithms 로그 → 거듭제곱의 반대

• 선형탐색 Linear Search 👌

def linear_search(element, some_list):
    for index in range(len(some_list)):
        if element == some_list[index]:
            return index
 
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

• 이진탐색 Binary Search -반복문

  def binary_search(element, some_list):
      start_index = 0
      end_index = len(some_list) - 1
   
      while start_index <= end_index:
          mid_index = (start_index + end_index) // 2
          if some_list[mid_index] == element:
              return mid_index
          elif some_list[mid_index] > element:
              end_index = mid_index
          else:
              start_index = mid_index
      return None
   
  print(binary_search(2, [2, 3, 5, 7, 11]))
  print(binary_search(0, [2, 3, 5, 7, 11]))
  print(binary_search(5, [2, 3, 5, 7, 11]))
  print(binary_search(3, [2, 3, 5, 7, 11]))
  print(binary_search(11, [2, 3, 5, 7, 11]))

• 리스트에 찾는 값이 없을 때 None을 리턴해야하는데 무한루프가 돈다. 어떻게 해결할지 고민중

• 이진탐색 -재귀 ❌