Suppose someone wants to know how many floors they can drop their iPhone from in a 100-story building before it will be broken. If they use a linear search algorithm, they will drop the iPhone from the first floor, then the second floor, then the third floor, until they reach a floor, maybe around the 75th floor, when the iPhone breaks. They do get an answer, but there is another searching algorithm that they can use to find the answer much more efficiently. That is the binary search algorithm.
Using the binary search algorithm, they would first go to the middle floor of the 100-story building. This means that they will drop the iPhone from the 50th floor. If their iPhone is not broken, they can eliminate all floors from the first to the 50th floor right away and only consider the floors from the 51st to the 100th floor. Then they can go to the 75th floor and drop off their iPhone. If it is broken, then they know their iPhone will be broken somewhere from the 50th to 75th floor. Basically, a binary search algorithm can eliminate half of the possibilities each time.
Binary search is to find a target in a sorted collection of items. In each round of the search, it compares the middle element to the target. If the target is larger than the middle element, the first half of the collection will be eliminated, and this process repeats until it finds the target.
Below are some leetcode problem illustrations on how we can translate binary search into code. There is a pattern for solving this kind of problem if you check out the answer to each question.
https://leetcode.com/problems/binary-search/
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return -1 if l == len(nums) or nums[l] != target else l
https://leetcode.com/problems/search-insert-position/
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
https://leetcode.com/problems/first-bad-version/
class Solution:
def firstBadVersion(self, n: int) -> int:
l = 1
r = n
while l < r:
mid = (l + r) // 2
if isBadVersion(mid):
r = mid
else:
l = mid + 1
return l
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
if numbers[l] + numbers[r] == target:
return [l + 1, r + 1]
if numbers[l] + numbers[r] > target:
r -= 1
else:
l += 1
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] <= nums[r]:
r = mid
else:
l = mid + 1
return nums[l]
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r and nums[l] == nums[r]:
l += 1
while l < r:
mid = (l + r) // 2
if nums[mid] <= nums[r]:
r = mid
else:
l = mid + 1
return nums[l]
https://leetcode.com/problems/find-peak-element/
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] >= nums[mid + 1]:
r = mid
else:
l = mid + 1
return l
https://leetcode.com/problems/sqrtx/
class Solution:
def mySqrt(self, x: int) -> int:
ans = 0
l = 1
r = x
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
ans = [-1, -1]
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if l < len(nums) and nums[l] == target:
ans[0] = l
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid
if l > 0 and nums[l - 1] == target:
ans[1] = l - 1
return ans
https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
class Solution:
def isPossible(self, weights, load, days):
cnt = 1
weigtAllocated = 0
for i in range(len(weights)):
if(weigtAllocated > load):
return False
weigtAllocated += weights[i]
if(weigtAllocated > load):
cnt += 1
weigtAllocated = weights[i]
return cnt <= days
def shipWithinDays(self, weights: List[int], days: int) -> int:
if days > len(weights):
return -1
l = max(weights)
r = sum(weights)
res = 0
while l <= r:
mid = (l + r) // 2
if self.isPossible(weights, mid, days):
res = mid
r = mid - 1
else:
l = mid + 1
return res
https://leetcode.com/problems/magnetic-force-between-two-balls/
class Solution:
def check(self, mid, m, position):
temp_pos = position[0]
temp_cnt = 1
for i in range(len(position)):
if position[i] >= temp_pos + mid:
temp_pos = position[i]
temp_cnt += 1
if temp_cnt < m:
return False
return True
def maxDistance(self, position: List[int], m: int) -> int:
position.sort()
l = 0
r = position[-1]
res = 0
while l <= r:
mid = (l + r) // 2
if self.check(mid, m, position):
res = mid
l = mid + 1
else:
r = mid - 1
return res