# 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;
}
}
``````
2. 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;
}
}
``````
2. 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;
}
}
``````
2. 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;
}
}
``````