06 - Binary Search
Uploaded by
abdklaib23306 - Binary Search
Uploaded by
abdklaib233Competitive Programming (0907548)
Binary Search
Instructor: Dr. Fahed Jubair
Computer Engineering Department
University of Jordan
Binary Search
• An O(log n) search algorithm that is used to search for a given
element in a sorted array
• A common implementation is shown below:
© All Right Reserved
Another Implementation
• Another way to implement binary search is to go through the
array from left to right making jumps
• The initial jump length is n/2, then the next one is n/4, then n/8,
and so on till finally the jump length is 1
© All Right Reserved
Finding Minimum Solutions
• Assume a problem with a function 𝑣𝑎𝑙𝑖𝑑(𝑥) that returns true if
𝑥 is a valid solution and false otherwise
• Binary search can be used to find the minimum 𝑧 such that
𝑣𝑎𝑙𝑖𝑑(𝑥) = 𝑓𝑎𝑙𝑠𝑒 when 𝑥 < 𝑧, and 𝑣𝑎𝑙𝑖𝑑(𝑥) = 𝑡𝑟𝑢𝑒 when
𝑥≥𝑧
𝑣𝑎𝑙𝑖𝑑(𝑥)
The goal is to
find this 𝑧
𝑡𝑟𝑢𝑒
𝑓𝑎𝑙𝑠𝑒
𝑥
𝑧
© All Right Reserved
Example
Find Minimal Processing Time?
• Consider a problem where our task is to process 𝑘 jobs using 𝑛
machines. Each machine 𝑖 is assigned an integer 𝑝! : the time to
process a single job. What is the minimum time to process all the
jobs?
• For example, suppose that 𝑘 = 8, 𝑛 = 3 and the processing times
are 𝑝" = 2, 𝑝! = 3, and 𝑝! = 7
• In this case, as shown below, the minimum processing time is 9
© All Right Reserved
Solution Implementation
• At most, each machine 𝑖 can
execute 𝑥/𝑝! jobs
• Therefore, 𝑥 is a valid solution
if ∑(𝑥/ 𝑝! ) ≥ k
• We can use binary search to
find the minimum value of k
• The input z is an initial upper
bound of solution
• Example: a valid upper
bound is 𝑘 ∗ 𝑝"
© All Right Reserved
Activities
Solve the following problems:
1. Factory Machines (problem link)
2. Sum of Three Values (problem link)
© All Right Reserved
Summary
• Binary search is an efficient method for finding an element in a
sorted array
• Binary search is useful for solving problems that can be reduced to
yes/no questions or when searching for thresholds.
• Binary search is also useful for range search and finding solutions in
mathematical problems
