1，二分法查找，插入元素位置
/**
* 二分法查找元素，没有则返回-1
* 扩展，在数组中插入某个元素,插入的元素的下标位置即为left值
* @author xhq
*
*/
public class halfSearch {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = { 2, 4, 6, 7, 8, 9, 11, 13};
int index = halfSearch(arr, 6);
int insert = halfSearchInsert(arr, 6);
System.out.println(index);
System.out.println(insert);
}
public static int halfSearch(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
public static int halfSearchInsert(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
}
2，数组旋转，求最小值问题
public class N08 {
/**
* 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。
* 例如数组{3,4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
* 1，假设数组第0个元素移到后面？降序或者升序？
* 2，对于1 0 1 1 1 1 1 1 1...的处理？
* 3，非旋转数组怎么判断?
* 4，以下算法只适用于一串升序数组的旋转。
* 参考：http://zhedahht.blog.163.com/blog/static/25411174200952765120546/
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 3, 4, 5, 1, 2 };
int min = searchMin(arr);
System.out.println(min);
}
private static int searchMin(int[] array) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (right - left == 1)
break;
if (array[mid] >= array[left])
left = mid;
else {
right = mid;
}
}
return array[right];
}
}
参考
旋转数组的最小元素
