1.普通的二分查找
对一个已经排好序的数组array（元素不重复），给定一个数target，返回这个数在数组中的下标，如果不存在则返回-1。
代码：
/**
* 二分查找(元素不重复)
* @param array
* @param target
* {0,1,2,3,4}
*/
public static int binarySearch(int[] array,int target){
int left = 0;
int right = array.length -1;
while(right >= left){
int mid = (right + left)/2;
int midNum = array[mid];
if (midNum > target){
right = mid -1;
}else if (midNum < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
2.二分查找变种（一）
对于一个已经排好序的数组，数组中的元素有重复，给定一个数target，要求返回其第一次出现在数组的下标，不存在则返回-1。例如{0,1,2,3,3,3}，target=3，最终返回结果为3。
代码：
/**
* 查找第一次出现的位置
* @param array
* @param target
* @return
* {0,1,2,3,4,4,4}
*/
public static int binarySearchFirst(int[] array,int target){
int left = 0;
int right = array.length -1;
while(right > left){
int mid = (right + left)/2;
int midNum = array[mid];
if (midNum < target){
//中间数小于目标数
left = mid + 1;
}else{
//中间数大于等于目标数
right = mid;
}
}
if(array[left]!=target){
return -1;
}else{
return left;
}
}
3.二分查找变种（二）
对于一个已经排好序的数组，数组中的元素有重复，给定一个数target，要求返回其最后一次出现在数组的下标，不存在则返回-1。例如{0,1,2,3,3,3}，target=3，最终返回结果为5。
代码：
/**
* 查找最后一次出现的位置
* @param array
* @param target
* @return
* {0,1,2,3,4,4,4}
*/
public static int binarySearchLast(int[] array,int target){
int left = 0;
int right = array.length -1;
while(right > left){
int mid = (right + left + 1)/2;
int midNum = array[mid];
if (midNum > target){
right = mid - 1;
}else{
left = mid;
}
}
if (array[left] == target){
return left;
}else{
return -1;
}
}
4.二分查找变种（三）
对于一个数组，先是单调递增，然后单调递减，怎么找到分界线的那个元素？例如：{0,1,2,3,4,5,6,7,8,9,5,4,3,2,1,0}，返回的就是数字9的下标。
代码：
/**
* 如果一个数组，先是单调递增，然后单调递减，怎么找到分界线的那个元素？
* @param array
* @return
* {0,1,2,3,4,5,6,7,8,9,5,4,3,2,1,0}
* 思路：
* 折半 看是否是 左边比他小 右边比他大 OK 抛弃左边 left = mid
* 是否是 右边比他大，左边比他小 OK 抛弃右边 right = mid
* 只剩下 左边比他小，右边也比他小 OK 就是这个数 返回下标即可
*/
public static int find(int[] array){
int left = 0;
int right = array.length - 1;
int mid;
int midNum;
while(left < right){
mid = (left + right) / 2;
midNum = array[mid];
if (array[mid - 1] < midNum && array[mid + 1] > midNum){
//左边比他小 右边比他大 是递增的
left = mid;
}else if (array[mid - 1] > midNum && array[mid + 1] < midNum){
//右边比他大，左边比他小 是递减的
right = mid;
}else{
return mid;
}
}
return -1;
}
4.二分查找变种（四）
求旋转数组的分界线问题。旋转数组
如果将一个有序递增的数组前X位平移到数组末尾，如何找出数组的分界线？例如：[1,2,3,4,5,6]将前3个元素平移到最后，使其成为[4,5,6,1,2,3]，需要找到6这个元素？
思路：这道题如果采用循环从第一个位置开始找的方式，很容易求解，但是效率不高。采用折半的思想，能够较快的求解，跟上道题一样，还是先二分，然后判断数据，最后抛弃一半长度的数组。不过这道题的判断条件多一个，判断的时候考虑旋转数组的特性即可。具体求解方法请看代码。
代码：
/**
* 如果将一个有序递增的数组前X位平移到数组末尾，如何找出数组的分界线？
* 比如[1,2,3,4,5,6]将前3个元素平移到最后，使其成为[4,5,6,1,2,3]，需要找到6这个元素
* @param array
* @return
*/
public static int find2(int[] array){
int left = 0;
int right = array.length - 1;
int mid;
int midNum;
while(left < right){
mid = (left + right) / 2;
midNum = array[mid];
if (array[mid - 1] < midNum && array[mid + 1] > midNum && array[left] > midNum){
//数组的第一个数比他大，抛弃右边
right = mid;
}else if (array[mid - 1] < midNum && array[mid + 1] > midNum && array[left] < midNum){
//数组的第一个数比他小，抛弃左边
left = mid;
}else if (array[mid - 1] < midNum && array[mid + 1] < midNum){
return mid;
}else{
return -1;
}
}
return -1;
}
网友评论