Binary search variations/applications

1. find target position, return index, or -1 if not exist

public int BinarySearch(int[] a, int l, int r, int key) { // find target position while (l <= r) { int m = l+(r-l)/2; if (a[m] == key) return m; if (a[m] > key) r = m-1; else l = m+1; } return -1; } }

1. find target insert position, return insert index; if target is in the array, the return value is index of the target, if not, return value is the insert position

this method can be used for both search and insert

public int BinarySearch(int[] a, int l, int r, int key) { // find target insertion position while (l <= r) { int m = l+(r-l)/2; if (a[m] >= key) r = m-1; else l = m+1; } return l; }

1. find leftbound of target, return target index; return -1 if not exist

public int BinarySearch(int[] a, int l, int r, int key) { while (l <= r) { int m = l+(r-l)/2; if (a[m] >= key) r = m-1; else l = m+1; } if (l >= 0 && l < a.length && a[l] == target) { return l; return -1; } }

1. find rightbound of target, return target index; return -1 if not exist

public int BinarySearch(int[] a, int l, int r, int key) { while (l <= r) { int m = l+(r-l)/2; if (a[m] <= key) l = m+1; else r = m-1; } if (r >= 0 && r < a.length && a[r] == target) { return r; return -1; } }

1. find minimum in rotated sorted array

Without Duplicates

public class Solution { public int findMin(int[] nums) { if (nums.length == 0) { return -1; } int left = 0, right = nums.length-1; while (left <= right) { int mid = left + (right-left)/2; if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) { return nums[left]; } if (nums[left] <= nums[mid]) { left = mid + 1; } else { right = mid; } } return -1; } }

1. if the target is dynamic, cant find exact equal condition to return

idea: use an extra variable to store the answer each time

Example: H index II

public class Solution { public int hIndex(int[] citations) { int start = 0; int end = citations.length-1; int len = citations.length; int result = 0; int mid; while(start <= end){ mid = start + (end-start)/2; if(citations[mid] >= (len - mid)){ result = (len-mid); end = mid-1; } else{ start = mid + 1; } } return result; } }