[Leet Code] Binary Search (이진탐색): 704.Binary Search, 278.First Bad Version, 35.Search Insert Position - Easy

* 이진 검색 알고리즘 포스팅

 

* Binary Search (문제 /코드)

* First Bad Version (문제 / 코드)

* Search Insert Position (문제 / 코드)

 

 이름에서 느낄 수 있듯이 아주 간단한 이진 탐색 문제인데 푸는데 while문을 언제 종료해야 할지 몰라서, 그리고 두 번째 문제는 도대체 문제가 뭔 뜻인지 이해가 안가서 easy 세 문제 푸는데 무려 네 시간을 소비했다.

알고리즘 2주 쉬었는데 이렇게 감이 떨어질 수 있다는게 놀라웠다. 머리의 문제인가..

 

그리고 티스토리 코드에디터 진짜 보기 싫음

 

Description

Binary Search & Search Insert Position

 The problems ask to find "target" number in the given array. If target number isn't there, needs to return -1(Binary Search) or the index where the target would be if it were inserted in order(Search Insert Position).

First Bad Version

 Find the integer "bad" using api in an integer range from 1 to n. When we put an integer smaller than "bad" into the api, it returns False. Else, it returns True.

 In the other words, it means among the numbers from 0 to n, to find the smallest number which return True when it's input into the api.

 

How to solve

 We can rotate the array from the first value to the last value but TC is O(n). So we need to narrow down the searching area. We can do it with Binary search algorithm because the input array is sorted.

 All 3 problems can be solved with the same code, but I used a bit different logic for the second problem for speed.

 

A basic concept of Binary search algorithm:

1. Set the whole given array as a searching area.

2. Compare the middle number of searching area with "target".

 - If the middle number is same with "target", return the idx of the middle num.

 - If the middle num > "target", move the searching area to left.

 - Else, move the searching area to right

3. Repeat 2 until the searching area has no value to search

 

Pseudo code

Binary Search & Search Insert Position

low, high = 0, len(nums)-1 #set the first searching area
mid = (low+high)//2
if nums[mid] == target : return mid
elif nums[mid] > target:
	high = mid-1 #mid ~ high is bigger than the target, so no need to search there
else:
	low = mid+1 #low ~ mid is smaller than the target, so no need to search there
break if low > high #Means the loop kept minusing high or plusing low but the target is not found

#Binary Search
return -1

#Search Insert Position
"""
While loop terminates(low>high) when the last step was the below case:
1. low and high was pointing the same value = searching area has one value only
(because each step of the loop, either low and high increase 1 only)
2. mid was also pointing the same value because high+low//2 = mid = 2high//2
3. target is bigger than mid because low increases in this case only
4. low becomes low+1 and it means it's same with mid+1=high+1
5. It's bigger than high, breaks the loop
idx should be mid+1 following 3 - which is same with the current low. So retrun low
"""

First Bad Version

low, high = 1, n #set the first searching area
mid = (low+high)//2
if api(mid) == True :
	high = mid #"bad" can be same or smaller than mid, move searching area to the left
else:
	low = mid+1 #"bad" is bigger mid, move searching area to the right
break if low == high #Means high and low is pointing one number == bad

"""
While loop terminates when the last step was the below case:
1. high was low+1, mid == low
2-1. If api(mid) is True (= api(low) is True):
 - high decreases 1. It means high = low
2-2. If api(mid) is False (= api(low) is False):
 - low increases 1. It means low = high
3. breaks the loop

Note that the result of api(high) is always True because:
- At the first time, it was the biggest number(=n)
- It was changed to mid when api(mid) returned True only.

So after the loop terminates, low == high, and api(low) == api(high) == True.
"""
return low

 

TC = O(logn)