课程尚未开始
请大家耐心等待
关注微信公共账号，获得最新面试题信息及解答
Facebook: [Link]
com/ninechapter
Weibo:
[Link]
Binary Search & Sorted Array
九章算法IT求职面试培训课程 第2章
[Link]
Binary Search
Classical Binary Search
Given an sorted integer array - nums, and an
integer - target. Find the any/first/last
position of target in nums, return -1 if target
doesn’t exist.
public int binarySearch(int[] nums, int target)
How we do binary search?
start end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
2. Find 8, mid=4, 2, 3. Find it!
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
2. Find 8, mid=4, 2, 3. Find it!
3. Find 14, mid=4
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
2. Find 8, mid=4, 2, 3. Find it!
3. Find 14, mid=4, 6
How we do binary search?
start mid end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
2. Find 8, mid=4, 2, 3. Find it!
3. Find 14, mid=4, 6, 5
How we do binary search?
start, mid
end
index 0 1 2 3 4 5 6 7 8
nums 2 3 5 8 13 21 34 55 89
1. Find 5, mid=4, 2. Find it!
2. Find 8, mid=4, 2, 3. Find it!
3. Find 14, mid=4, 6, 5, 4. Return -1
Recursion or While-Loop?
Binary Search
A generic binary search template
[Link]
[Link]
Keypoints:
1. start + 1 < end
2. start + (end - start) / 2
3. A[mid] ==, <, >
4. A[start] A[end] ? target
Search for a range
[Link]
[Link]
range/
Search Insert Position
[Link]
position/
[Link]
position/
Search a 2D Matrix
[Link]
matrix/
[Link]
matrix/
Search a 2D Matrix II
[Link]
ii/
[ 0, 1, 2, 4]
[ 1, 2, 6, 9]
[ 3, 5, 7,10]
[ 7, 8, 9,11]
Search a 2D Matrix II
Quadrate Search
[ 2, 4 ]
[ 0, 1, 2, 4] [ 0, 1, 2, 4] [ 5, 7 ]
[ 1, 2, 5, 7] find 7 [ 1, 2, 5, 7]
[ 3, 5 ]
[ 3, 5, 7,10] [ 3, 5, 7,10]
[ 7, 8 ]
[ 7, 8, 9,11] [ 7, 8, 9,11]
[ 7, 10]
[ 9, 11]
Search in a 2D Matrix
Search in a 2D Matrix
Search in a 2D Matrix
First Bad Version
[Link]
Find Peak Element
[Link]
5 minutes break
Search in Rotated Sorted Array
[Link]
sorted-array/
[Link]
rotated-sorted-array/
Search in Rotated Sorted Array II
[Link]
sorted-array-ii/
Linear algorithm, go for-loop!
Find Minimum in Rotated
Sorted Array
[Link]
minimum-in-rotated-sorted-array/
Find Minimum in Rotated
Sorted Array II
[Link]
minimum-in-rotated-sorted-array-ii/
Sorted Array
Remove Duplicates from Sorted Array
I, II
[Link]
[Link]
ii/
Merge Sorted Array
[Link]
Merge Sorted Array II
[Link]
ii/
[Link]
array/
Median of Two Sorted Arrays
[Link]
sorted-arrays/
[Link]
two-sorted-arrays/
Recover Sorted Array
[Link]
sorted-array/
Rotate String
[Link]
Reverse Words in a String
[Link]
string/
Conclusion
Binary Search
-- Exclude half every time
Sorted Array
-- If array is sorted, try binary search
-- If array is not sorted, try sort it first
