Binary search template by jiuzhang
http://www.jiuzhang.com/solutions/binary-search/
Note: if question is not complex, try non-recursive method firstly, then recursive method, which depends on the interviewer.
When need Binary search?
- You need to optimize a brute-force method of O(n) to a better one
- Sorted array or rotated sorted array
How Binary search?
- Find first position of …
- Find last position of …
Key points:
- start + 1 < end: to have situations where only have start and end left, or one number (start/end) left
- mid = start + (end – start) / 2, to avoid the overflow problem, for example, start and and end are both a very large number close to the MAX_Integer
- To find the first, we need to specify two parts: if (nums[mid] == target) end = mid; then if (nums[start] == target) return start goes firstly.
- To find the last, we need to specify two parts: if (nums[mid] == target) start = mid; then if (nums[end] == target) return end goes firstly.
Four important points to notice:
- start + 1 < end
- start + (end – start) / 2
- A[mid] ==, <, >
- A[start] A[end] ? target
Non-recursive Binary search:
class Solution { /** * @param nums: The integer array. * @param target: Target to find. * @return: The first position of target. Position starts from 0. */ public int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0, end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { end = mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; } }
Recursive Binary search:
public static int binarySearch(int[] nums, int target) { return binarySearch(nums, 0, nums.length - 1, target); } private static int binarySearch(int[] nums, int start, int end, int target) { if (start > end) return -1; int mid = start + (end - start) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { return binarySearch(nums, mid + 1, end, target); } return binarySearch(nums, start, mid - 1, target); }