1、概念
- 概念：二分查找也稱折半查找（Binary Search）捆探，它是一種效率較高的查找方法然爆。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)黍图，而且表中元素按關(guān)鍵字有序排列曾雕。
2、前提
必須采用順序存儲(chǔ)結(jié)構(gòu)助被。
必須按關(guān)鍵字大小有序排列剖张。
3、思想
- 思想：每次去找中間的那個(gè)元素比較大小揩环，每次可以減少一半元素比較搔弄。
4、過(guò)程
- 定義最小丰滑，中間顾犹，最大索引：min，mid褒墨，max
- 計(jì)算中間索引
- 那中間索引和查找元素索引比較炫刷，相等：返回中間索引；小于：左邊查找 max = mid -1郁妈；大于：右邊查找 min = mid + 1浑玛；
- 重新獲取最小索引和最大索引
- 重復(fù)前面的步驟，直到找到匹配索引
4噩咪、復(fù)雜度
總共有n個(gè)元素锄奢，每次查找的區(qū)間大小就是n，n/2剧腻，n/4拘央，…，n/2^k（接下來(lái)操作元素的剩余個(gè)數(shù)）书在，其中k就是循環(huán)的次數(shù)灰伟。
由于n/2^k
取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2為底栏账，n的對(duì)數(shù)）帖族，所以
時(shí)間復(fù)雜度：可以表示O(n)=O(logn)
5、實(shí)現(xiàn)方式
1. 非遞歸方式
package com.fsj;
public class Test10 {
public static void main(String[] args) {
int[] arr = { 11, 22, 33, 44, 55, 66, 77 };
System.out.println(search(arr, 55)); // 4
}
public static int search(int[] arr, int value) {
int min = 0;
int max = arr.length - 1;
while (min <= max) {
int mid = (min + max) / 2;
if (arr[mid] > value) {
max = mid - 1;// 比中間索引的數(shù)字大則關(guān)鍵字在左區(qū)域
} else if (arr[mid] < value) {
min = mid + 1;// 比中間索引的數(shù)字小則關(guān)鍵字在右區(qū)域
} else {
return mid; // 找到直接返回索引
}
}
return -1; // 沒(méi)找到,返回-1
}
}
2. 遞歸方式
package com.fsj;
public class Test10 {
public static void main(String[] args) {
int[] arr = { 11, 22, 33, 44, 55, 66, 77 };
System.out.println(search(arr, 44, 0, arr.length - 1)); // 3
}
public static int search(int[] arr, int value, int min, int max) {
int mid = (min + max) / 2;
if (value < arr[min] || value > arr[max] || min > max) {
return -1;
}
if (arr[mid] < value) {
return search(arr, value, mid + 1, max);
} else if (arr[mid] > value) {
return search(arr, value, min, mid - 1);
} else {
return mid;
}
}
}
