Binary search LeetCode-704 문제

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

오름차순으로 정렬된 정수 숫자의 배열과 정수 대상을 숫자로 검색하기 위한 함수를 작성합니다. 대상이 있으면 인덱스를 반환합니다. 그렇지 않으면 -1을 반환합니다.

런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

 

Example 1:예시

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2: 예시

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

Constraints: 제약조건

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

class Solution{
public:
	int search(vector<int>& nums, int target)
	{
		int left = 0;
		int right = nums.size() - 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;
			}
		}return -1;
	}
};

binary search 를 위 코드를 보면 이해 할 수 있다.

 

쉽게 말해 pivot 을 기준으로 찾는 값이 큰지 작은지를 구분하여 O(log n) 의 TimeComplexity를 가지게 해주는 방식이다.

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문