### 主要收获2

Divide Two Integer开始，到Search for a Range,Search in Rotated Sorted Array，再到今天的Search Insert Position连续的二分查找问题。写了好几遍不同的实现，也都Accepted了，但离最优实现总是还差一点。

### 题目

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0


### 递归二分查找 $O(\log_{}{n})$

1. 如果表中存在目标数，返回目标数在表中的下标。
2. 如果表中不存在目标数，返回表中小于目标数的元素的数量。（和返回元素应该插入的位置是一回事）
3. 假设表中没有重复的数字。

#### 代码

public class Solution {
public int searchInsert(int[] nums, int target) {
if (nums.length == 0) { return 0; }
return searchInsertRecur(nums,target,0,nums.length-1);
}
public int searchInsertRecur(int[] nums, int target, int low, int high) {
if (low >= high) {
return (nums[low] >= target)? low : ++low;
}
int median = low + ( (high - low) >> 1 );
if (nums[median] < target) {
return searchInsertRecur(nums,target,median+1,high);
} else if (nums[median] > target) {
return searchInsertRecur(nums,target,low,median-1);
} else {
return median;
}
}
}


### 迭代版二分查找 $O(\log_{}{n})$

#### 代码

public class Solution {
public int searchInsert(int[] nums, int target) {
if (nums.length == 0) { return 0; }
int low = 0, high = nums.length-1;
while (low < high) {
int median = low + ( (high - low) >> 1 );
if (nums[median] < target) { low = median + 1; }
if (nums[median] > target) { high = median - 1; }
if (nums[median] == target) { return median; }
}
return (nums[low] >= target)? low : ++low;
}
}


### 更简洁的 base case

#### 代码

public class Solution {
public int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length-1;
while (low <= high) {
int median = low + ( (high - low) >> 1 );
if (nums[median] < target) { low = median + 1; }
if (nums[median] > target) { high = median - 1; }
if (nums[median] == target) { return median; }
}
return low;
}
}


### 推广到有重复元素的数组中

#### 迭代版代码

public class Solution {
public int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length-1;
while (low <= high) {
int mid = low + ( (high - low) >> 1 );
if (nums[mid] < target) { low = mid + 1; }
if (nums[mid] >= target) { high = mid - 1; }
}
return low;
}
}


#### 递归版代码

public class Solution {
public int searchInsert(int[] nums, int target) {
return firstOccurrenceRecur(nums,target,0,nums.length-1);
}
public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
if (low > high) { return low; }
int mid = low + ( (high - low) >> 1 );
if (nums[mid] < target) {
return firstOccurrenceRecur(nums,target,mid + 1,high);
} else {
return firstOccurrenceRecur(nums,target,low,mid-1);
}
}
}