1.Definition
Binary Search is a search algorithm that finds the position of a target value within a sorted array (or an array arranged in a special way).
2.Methods
The key point of binary search is to maintain a range and make sure the target number is in the range. The search process is to shrink the range in multiple iterations until its size is 1 or find it.
In each iteration, half (or 1/n) the range's size. Use the middle element's value to decide it is the left half range or the right half range.
3 key steps:
1) identify the range (sometimes we might need to construct the range)
2) decide the appropriate way to shrink the range
3) check potential endless loops
e.g., find the index of 5 in the array 0-9
Note: We can use two pointers (lo, hi) to represent the range.
3.When do we apply binary search?
1.Index-based search problem: 3 basic BS problems and corresponding methods to shrink the range.
[question] Given a sorted array/matrix, try to find a specific element.
[identify the range] In this kind of question, the range is the index range [0, arr.length-1].
[methods of shrinking the range]
We will discuss how to shrink the range in the 3 types of BS problem. Let's assume that the current range is [lo, hi], and mid = lo+(hi-lo)/2.
[type 1] Find the only/any one problem
[Typical example]: find the index of 5 in the array [0,1,2,3,4,5,6]
[Explain]:
if array[mid] < target, shrink the range as [lo, mid-1];
else array[mid] > target, shrink the range as [mid+1, hi];
else return mid;
[Questions]
74. Search a 2D Matrix
240. Search a 2D Matrix II
374. Guess Number Higher or Lower
[type 2] Find the first one
[Typical example]: find the index of the first 5 in the array [0,1,1,1,2,3,4,5,5,6]
[Explain]:
if array[mid] == target, shrink the range as [lo, mid]; //*
else if array[mid] < target, shrink the range as [mid+1, hi];
else shrink the range as [lo, mid-1];
//* It is possible to trigger an endless loop. So we need to check whether lo==mid, if it is, break and jump out of the loop.
[Questions]
153 Find Minimum in Rotated Sorted Array
35 Search Insert Position
275. H-Index II
278. First Bad Version
[type 3] Find the last one
[Typical example]: find the index of the last 5 in the array [0,1,1,1,2,3,4,5,5,6]
[Explain]:
if array[mid] == target, shrink the range as [mid, hi];
else if array[mid] < target, shrink the range as [lo, mid-1];
else shrink the range as [mid+1, hi];
[identify the range] In this kind of question, the range is the index range [0, arr.length-1].
[type 4 - combination type] questions involves two or three types above
153 Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II
33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II
34. Search for a Range
2.Advanced binary search: shrink the range in a specific way
[calculation problem]
[Identify the range]: given a number n, the range is [0,n]
tips: >>1 <<1 corresponds to /2, *2, which can be used in binary operations.
[questions]
367. Valid Perfect Square
29. Divide Two Integers
69 Sqrt(x)
50. Pow(x, n)
287. Find the Duplicate Number
[Other typical array/matrix related binary search problem]
302. Smallest Rectangle Enclosing Black Pixels
[key point]
1. [identify the range]: contstruct an array, array[i] represents in the column i of the matrix, there is at least one 1. the array will be like [00011111000].
2. [methods of shrinking the range]: find the first 1's and last 1's index.
354. Russian Doll Envelopes
4. Median of Two Sorted Arrays
1.[identify the range] the range contains two sorted array, [arr1] and [arr2]
2.[methods of shrinking the range]:
363. Max Sum of Rectangle No Larger Than K
162. Find Peak Element
2.[methods of shrinking the range]:
No comments:
Post a Comment