二分查找的变形(1)

1.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引
如果目标值不在数组中，返回它将会被按顺序插入的位置索引。
思路：
如果值不存在，我们就不会查找到该值所对应的索引，在极端条件下，
当left == right时，如果该位置下的值 还不是 我们的目标值的话，
如果该位置下的值 比 目标值小，left++，说明，目标值应该在此时left所指向的位置。
如果该位置下的值 比 目标值大，right—，说明，目标值在此时所对应的left所指向的位置。
例：
1 3 5 7 9 11
0 1 2 3 4 5
我们的目标值 是 8
当left == right == middle== 3时，此时arr[3] = 7
和我们的目标值进行比较，arr[3] < 8
left = middle+1 即left = 4.
此时left 正好是我们目标值val 应该插入的位置

若我们的目标值为4
当left == right ==middle==2时，此时arr[2] = 5
和我们的目标值进行比较，arr[2] = 5 > 4
right = middle -1 即right=1
但此时，left正好是我们目标值val应该插入的位置

*/
public class MiddleFind2 {
public static int Find(int arr[],int val){
int left = 0;
int right = arr.length-1;
while(left <= right){
int middle = (right-left >>1) + left;
if (arr[middle] >val){
right = middle - 1;
}else if (arr[middle] < val){
left = middle + 1;
}else if (arr[middle] == val){
return middle;
}
}
return left;
}
public static void main(String[] args) {
int arr[] = new int[]{1,3,5,7,9,11};
System.out.println(Find(arr, 3));
}
}