二分查找，如何用最勝記憶體的方式實作快速查找
針對有序資料集合的查找算法，二分查找。
問題：假設我們有1000萬個整數資料，每個資料占8個位元組，如何設計資料結構和算法快速判斷某個整數是否出現在這1000萬資料中，
最簡單的辦法就是将資料存儲在數組中，記憶體占用差不多80M，符合記憶體限制，是以，先對資料從小到大排序，然後利用二分查找算法，就可以快速查找想要的資料。
二分查找針對的是一個有序的資料集合，查找思想類似分治思想，每次都通過跟區間的中間元素對比，将待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間縮小為0
二分查找時間複雜度低，O(logn)，
二分查找最簡單的就是有序數組中不存在重複元素。
二分查找依賴的是順序表結構，就是數組。還針對的是有序資料。
二分查找隻能再插入，删除不頻繁，一次排序多次查找的場景中，針對動态變化的資料集合，二分查找将不再适用。
資料量太小不适合二分查找。
資料量太大也不适合二分查找，因為底層依賴數組這種資料結構，而數組為了支援随機通路，要求記憶體空間連續，對記憶體的要求苛刻。
使用遞歸實作二分查找
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
if(key<arr[low] || key> arr[high] || low > high){
return -1;
}
int middle = low + ((high - low)>>1);
//middle = (low + high) / 2; 這種寫法有可能會導緻溢出，比如low很大，high也很大，之和就溢出了。
if(arr[middle] > key){
return recursionBinarySearch(arr,key,low,middle);
}
else if(arr[middle] < key){
return recursionBinarySearch(arr,key,middle + 1,high);
}else {
return middle;
}
}
普通的二分查找。
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length -1;
int middle = 0;
if(key < arr[low] || key> arr[high] || low > high){
return -1;
}
while(low <=high){
middle = low + ((high - low)>>1);
//middle = (low + high) / 2; 這種寫法有可能會導緻溢出，比如low很大，high也很大，之和就溢出了。
if(arr[middle] > key){
high = middle -1;
}else if(arr[middle] < key){
low = middle + 1;
}else {
return middle;
}
}
return -1;
}
變體一，查找第一個值等于給定值的元素
public static int bsearchFirst(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (low < n && a[low]==value) return low;
else return -1;
}
第二種方法
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
變體二，查找第一個值等于給定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
變體三，查找第一個大于等于給定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
變體四，查找最後一個小于等于給定值的元素
public int bsearchFour(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
如果有序數組是一個循環有序數組，比如4.5.6,1,2,3這種情況。
//無重複元素
public int search(int[] nums, int target)
{
int start = 0,end = nums.length-1;
while(start<=end)
{
int mid = (start+end)/2;
if(target == nums[mid]){return mid;}
if(nums[start]<=nums[mid])//說明start-mid之間是有序的
{
if(nums[start]<=target && target<nums[mid])
{
end = mid-1;
}else
start = mid+1;
}else
{
if(target>nums[mid] && target<=nums[end])
{
start = mid+1;
}else
end = mid-1;
}
}
return -1;
}
//有重複數字
public boolean searchCycle(int[] nums, int target) {
int start = 0,end = nums.length-1;
while(start<=end)
{
int mid = (start+end)/2;
if(target == nums[mid]){return true;}
if(nums[mid]>nums[start])
{
if(target>=nums[start] && target<nums[mid])
{
end = mid-1;
}else
{
start = mid+1;
}
}else
if(nums[mid] == nums[start])
{
while(start<=mid)
{
if(nums[start] == target){return true;}
if(nums[start] != nums[mid])
{
break;
}
start++;
}
}else
{
if(target>nums[mid] && target<=nums[end])
{
start = mid+1;
}else
end = mid-1;
}
}
return false;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)