이진 검색을 사용하여 그룹에 임의의 값이 있는지 확인합니다

이미 많은 분들이 써주셨지만.
나는 글을 써서 나의 이해를 깊게 하려고 썼다.

문제.

바이너리 검색을 사용하여 다음 문제를 해결하십시오.
정렬 있음array=[1, 3, 5, 6, 9, 10, 13, 20, 26, 34]이 그룹에 임의의 값이 있는지 검색하는 코드를 만듭니다.
배열에 값이 없으면 값이 배열에 저장되지 않음을 표시합니다.
존재하면 배열의 몇 위를 표시합니다.

# 出力例1
検索したい数字を入力してください
5
5は配列の2番目に存在します

# 出力例2
検索したい数字を入力してください
8
8は配列内に存在しません

원래 바이너리 검색이 뭐예요?

정렬된 목록이나 배열의 데이터를 검색할 때 (같은 값이 없음)
검색할 값과의 크기 관계 사용
검색할 값이 중앙값의 오른쪽인지 왼쪽인지 확인하십시오
한쪽이 존재하지 않는지 확인하면서 검색하는 방법.
한 번의 처리에서 선택 항목이 반으로 바뀌기 때문에 처리 속도가 향상되기를 기대할 수 있다.
이분 탐색을 이분 검색이라고도 부른다.

어떤 느낌인지 대충 적어주세요.

검색하려는 값은 target입니다.
맨 왼쪽에 붙은 글자는 left,
맨 오른쪽에 붙은 글자는 right,
중간의 부가자 대입center.
참고로 이번 검색은 target=5입니다.
수조를 도표로 바꾸는 것은 다음과 같다.

그럼 실제로 해볼게요.
첫 번째 검색에서
left = 0
right = 9
중간의 부가가치는
center =(left+right)/2, 즉 center =4.
(사실 9를 2로 나누면 4.5인데 루비의 경우 정수/정수 = 정수(소수점 이하 반올림)이니 문제없다)
중간 값의 부가자를 알았기 때문에 검색하고 싶은 값이 비교적 많다.
array[center] = 9
target = 5
따라서aray[center]target.
이렇게 하면 앞으로 수색할 범위를 알 수 있다.다음 그림과 같습니다.회색은 검색 대상에 없습니다.

그림에서 보듯이 right에 변경이 생겼다.
한 센터가 왼쪽으로 변경됨
right = center - 1
물론 센터도 바뀔 거야.방법을 찾는 것은 처음과 같다.
center = (left + right)/2
그나저나 두 번째 계산은 센터=1.
그리고 처음과 같이 중앙값과 검색하고자 하는 값을 비교합니다.
array[center] = 3
target = 5
따라서aray[center]다음 검색 범위를 알고 있습니다.

이번에 레프트가 바뀌었어.센터 오른쪽에 있으니까.
left = center + 1
센터도 바뀔 거야.방법을 찾다.
center = (left + right)/2
그나저나 세 번째 계산이면 센터=2.
그리고 이전과 같이 중앙의 값과 검색하고자 하는 값을 비교한다.
array[center] = 5
target = 5
aray[center]=target, 검색이 끝났습니다.

응답 예

위에서 대략적으로 쓴 것을 정리하면서 다시 쓰다.

def binary_search(array, right, target)
  left = 0
  while left <= right
    center = (left + right) / 2
    if array[center] == target
      return center
    elsif array[center] > target
      right = center - 1
    else
      left = center + 1
    end
  end
  return -1 
end

array = [1, 3, 5, 6, 9, 10, 13, 20, 26, 34]  # 16行目

puts "検索したい数字を入力してください"  # 18行目
target = gets.to_i
elements_num = array.count - 1

result = binary_search(array, elements_num, target)  # 22行目

if result == -1  # 24行目
  puts "#{target}は配列内に存在しません"
else
  puts "#{target}は配列の#{result}番目に存在します "
end

보태다

binary_검색 방법에는 이진 검색에 대한 기술이 있습니다.
while 반복으로 미리 설정합니다.
반복적으로 적용되는 조건은 배열의 맨 왼쪽에 있는 추가 문자 (left) 가 배열의 맨 오른쪽에 있는 추가 문자 (right) 와 같을 때까지 (초과 후 while 내 처리를 하지 않음) 하기 때문에left<=right로 설정합니다.
aray[center]=target
센터의 값을 되돌려주고 리턴에서 방법 내 처리에서 벗어납니다.
20행의 요소num = array.count-1에서 그룹 맨 오른쪽에 있는 추가 문자를 얻습니다.
어쩌면 카운트가 아닐지도 몰라, length도 돼.

정렬된 배열이 없으면

配列名.sort 정렬이 가능합니다.

끝맺다

each 방법을 사용해 비교하는 방법도 있지만 배열 내용이 많을수록 2진법 검색이 편리하다.
그러고 보니 예전과 친구들 사이에서 유행했던 어떤 앱은 이 구조를 사용했죠.
자꾸 길어지는 것 같아.끝까지 같이 있어줘서 고마워요.