二分搜索（折半查找）是应用很广泛的一种算法，当出现有序序列时，我们可以立马想到能否可以用二分法，其写法也较为固定。我们可以把二分法视为分治的应用。但是如果不注意其变换条件也是很容易写错。下边给出了二分查找的非递归和递归写法，只要注意其边界判断和变换，代码很简单：
二分法的递归和非递归写法
package com.blog.binarysearch;
/**
* @Description: 二分法(二分搜索 折半查找) 有序序列的搜索 时间复杂度为O(logn)
* @Author: Jingzeng Wang
* @Date: Created in 15:56 2017/7/23.
*/
public class BinarySearchDemo {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 5, 7, 9, 11, 13};
System.out.println(binarySearch(nums, 11));
System.out.println(binarySearchRecursive(nums, 11, 0, nums.length - 1));
}
/**
* 二分 非递归版本
* <p>
* right = num.length left < right right = mid; 另一种写法
*
* @param nums 已排序数组
* @param keyNum 待查找数字
* @return 返回查找的索引位置 没有则返回-1
*/
public static int binarySearch(int[] nums, int keyNum) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
//int mid = start + (end - start) / 2; //直接平均可能溢出，可以用此算法
int mid = (left + right) / 2;
if (nums[mid] < keyNum) {
left = mid + 1;
} else if (nums[mid] > keyNum) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
/**
* 二分搜索的递归写法
*
* @param nums
* @param value
* @param left
* @param right
* @return
*/
public static int binarySearchRecursive(int[] nums, int value, int left, int right) {
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (nums[mid] < value)
return binarySearchRecursive(nums, value, mid + 1, right);
else if (nums[mid] > value)
return binarySearchRecursive(nums, value, left, mid - 1);
else return mid;
}
}
二分法的变形应用
二分法的变形很多种，但是只要掌握了二分的核心思想，将转移条件写正确，基本就可以解决这些问题。比如一个有序序列中药查找的那个数出现很多次，求第一个出现的位置，求它最后出现的位置，求第一个小于某个数的数的位置，求第一个大于某个数的位置等等，只要出现有序序列，我们就可以思考此问题可否用二分法解决。下边给出一个题：
统计一个数字在排序数组中出现的次数。
// hash表可以 遍历也可以 但是排序数组肯定有用 二分啊
// 二分的变形：找正好大于k的那个数的位置 与 正好小于k 的位置 然后相减 时间复杂度为 O(logn)
// 定位k第一次出现的位置 和 最后一次出现的位置
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if (array == null || array.length <= 0) {
return 0;
}
int left = 0;
int right = array.length - 1;
int mid1 = (left + right) >> 1;
// 找第一个k
while (left <= right) {
if (array[mid1] >= k) {
right = mid1 - 1;
} else {
left = mid1 + 1; // < left 是始终指向小于k的 最后也是+1获得第一个k
}
mid1 = (left + right) >> 1;
}
mid1 = left;
left = 0;
right = array.length - 1;
int mid2 = (left + right) >> 1;
//找最后一个k
while (left <= right) {
if (array[mid2] > k) {
right = mid2 - 1; // 大于k的 获得最后一个k
} else {
left = mid2 + 1;
}
mid2 = (left + right) >> 1;
}
mid2 = right;
return mid2 - mid1 + 1;
}
}
