二分查找java代碼

A. 用二分法查找（折半查找）java

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

B. 如何用java代碼實現在一個已排列好的數組中找出小於等於給定x的位數下標（用二分查找做）

importjava.util.Arrays;

importjava.util.Random;

publicclassTest{

publicint[]getRandom(intlen){

int[]nums=newint[len<=0?10:len];

Randomrandom=newRandom();

for(inti=0;i<nums.length;i++){

nums[i]=random.nextInt(100);

}

returnnums;

}

publicIntegergetIndex(int[]nums,intvalue,intstartIndex,intendIndex){

if(startIndex==endIndex){

returnstartIndex;

}

intindex=(startIndex+endIndex)/2;

if(nums[index]==value){

returnindex;

}elseif(startIndex+1==endIndex&&nums[endIndex]>value){

returnendIndex;

}elseif(nums[index]>value){

returngetIndex(nums,value,startIndex,index);

}else{

returngetIndex(nums,value,index,endIndex);

}

}

publicstaticvoidmain(String[]args){

Testtest=newTest();

intvalue=50;

intlen=10;

int[]nums=test.getRandom(len);

Arrays.sort(nums);

Integerindex=test.getIndex(nums,value,0,nums.length-1);

System.out.println(Arrays.toString(nums));

System.out.println(value);

System.out.println(index);

}

}

C. JAVA 二分查找

,在將100/。;2/2與20比較.collections，取一段已經排好序的數據段，不過由於針對必須是已經排好序的數據段進行操作.util。直到找出20，集合）進行操作的方法大多都封裝與java，有1-100數據，20<，推薦冒泡法
java中對數據段（數組二分查找原理，java開源，此方法操作速度較快;類下邊，也可以與我進行交流，qq，首先將100/2與20比較，演算法相當之精闢，依此類推
如;100/，需要查找20，樓主有興趣可以去看看他的源碼，用需要查找的數據與該數據段的1/。，使用較少;2處的數據進行比較;2，先將該數據段從中間切割開

D. 二分查找 為什麼 查找第一個數(7)是 會報異常:java.lang.StackOverflowError 各位大哥 看看下面代碼

.二分法，首先要求，必須是有序的，
然後是 關於查不到結果的判斷

如果 假設查找的是7，
依次查找的下標為 3，1，沒找到。。。
出現了一種情況： centerIndex > rightIndex 悲劇 這下好了，下面情況 你輸出一下 3個index你就知道咋回事兒了， 實際上是成了一個沒有出口 的遞歸運算， 必然會出現溢出棧的情況。。。。

E. 什麼叫java中的二分查找法

1、演算法概念。

二分查找演算法也稱為折半搜索、二分搜索，是一種在有序數組中查找某一特定元素的搜索演算法。請注意這種演算法是建立在有序數組基礎上的。

2、演算法思想。

①搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；

②如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

③如果在某一步驟數組為空，則代表找不到。

這種搜索演算法每一次比較都使搜索范圍縮小一半。

3、實現思路。

①找出位於數組中間的值，並存放在一個變數中（為了下面的說明，變數暫時命名為temp）；

②需要找到的key和temp進行比較；

③如果key值大於temp，則把數組中間位置作為下一次計算的起點；重復① ②。

④如果key值小於temp，則把數組中間位置作為下一次計算的終點；重復① ② ③。

⑤如果key值等於temp，則返回數組下標，完成查找。

4、實現代碼。

/**
*description:二分查找。
*@paramarray需要查找的有序數組
*@paramfrom起始下標
*@paramto終止下標
*@paramkey需要查找的關鍵字
*@return
*/
publicstatic<EextendsComparable<E>>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{
if(from<0||to<0){
("paramsfrom&lengthmustlargerthan0.");
}
if(from<=to){
intmiddle=(from>>>1)+(to>>>1);//右移即除2
Etemp=array[middle];
if(temp.compareTo(key)>0){
to=middle-1;
}elseif(temp.compareTo(key)<0){
from=middle+1;
}else{
returnmiddle;
}
}
returnbinarySearch(array,from,to,key);
}

F. 關於java的binarySearch（）方法

結果是-6的原因是在子串[2,3,4,5,6]中並未找到8這個數字。然後我們來看一下binrySearch的源碼

public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

可以從源碼中看到，真正的二分查找是在binarySearch0方法中進行的。每次循環都會計算出本輪的中間位置mid，以及獲取中間值midVal。當中間值小於key時，說明要找的值在右半邊，low等於mid+1，當中間值大於key說明在左半邊，high=mid-1,找到瞭然後開始下一輪。當等於時也就是找到了目標值，直接返回位置mid。如果最後找不到目標值，則返回-(low+1)。

再來看看具體問題的執行：

第一輪算出的mid是(1+5) >>>1 =2，midValue=3 < 8 ,low=3；

進入第二輪mid為（3+5）>>>1 =3,midValue=4 < 8 ,low=4；

進入第三輪mid為（4+5）>>>1 = 4，midValue=5 < 8,low=5; 此時low==high跳出while循環 返回-（5+1）即-6.

拓展知識

二分查找的流程如下圖：

G. 用Java語言編寫對整型數組進行二分查找的程序。

public class BinarySearchDemo {

public static void main(String[] args) {
int[] a = new int[]{1,5,7,9,11,18,23,48,69};
int point = new BinarySearchDemo().binarySearch(a, 23);

if(point == -1)
System.out.println("在數組中未查找到數23");
else
System.out.println("數字23是數組中第 " + (point + 1) + " 位數");

}

/**
* 二分法查找一個整數在整型數組中的位置
*
* 演算法思路：首先得到數組a的最小值和最大值的下標，分別是：low和high，接著求出值位於數組中間那個數的下標middle
* 然後再將這個middle對應的數組中的數和待查找的數num進行比較，如果相等，則表示已查找到，如果num < a[middle]
* 則說明num位於a[low]和a[middle]之間，於是將a[middle - 1]設為較大值，繼續求出此時對應的a[middle]，
* 再進行比較，其他情況可依次類推。一直到low=high，如果此時還沒有在數組a中查找到，則說明該數組a中沒有值num，返回-1
*
* @param a 給定的整型數組
* @param num 待查找的數 num
*
* @return 返回整數num在數組a中的位置下標，如果未查找到則返回-1
* */
public int binarySearch(int[] a,int num){
int low = 0;
int high = a.length - 1;

while(low <= high){
int middle = (low + high) / 2;
if(num == a[middle])
return middle;
else if(num < a[middle])
high = middle - 1;
else
low = middle + 1;
}

return -1;
}

}

程序基本上就是這樣了，其中注釋中有詳細的解釋說明

H. 二分查找法的判定樹有什麼特點能不能用一個公式直接求出樹的深度

演算法思想：

將數列按有序化(遞增或遞減)排列，查找過程中採用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。

折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。

演算法步驟描述：

step1 首先確定整個查找區間的中間位置
mid = （ left + right ）/ 2

step2 用待查關鍵字值與中間位置的關鍵字值進行比較；

若相等，則查找成功

若大於，則在後（右）半個區域繼續進行折半查找

若小於，則在前（左）半個區域繼續進行折半查找
Step3 對確定的縮小區域再按折半公式，重復上述步驟。最後，得到結果：要麼查找成功， 要麼查找失敗。
折半查找的存儲結構採用一維數組存放。

折半查找演算法舉例

對給定數列（有序），按折半查找演算法，查找關鍵字值為30的數據元素。

折半查找的演算法討論：

優點: ASL≤log2n，即每經過一次比較,查找范圍就縮小一半。經log2n 次計較就可以完成查找過程。

缺點：因要求有序，所以要求查找數列必須有序，而對所有數據元素按大小排序是非常費時的操作。另外，順序存儲結構的插入、刪除操作不便利。

考慮：能否通過一次比較拋棄更多的部分（即經過一次比較，使查找范圍縮得更小），以達到提高效率的目的。……？

可以考慮把兩種方法（順序查找和折半查找）結合起來，即取順序查找簡單和折半查找高效之所長，來達到提高效率的目的？實際上這就是分塊查找的演算法思想。

例如：[問題分析] 由於數據按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.

Java風格的代碼舉例：
//使用折半法進行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);

return nIndex;
}

二分查找的性能說明

雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費 O(n lg n) 的時間。
二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
對那些查找少而又經常需要改動的線性表，可採用鏈表作存儲結構，進行順序查找。鏈表上無法實現二分查找

二分查找的C#實現代碼：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失敗
}
static void Main(string[] args)
{
Console.WriteLine("請輸入10個遞增數字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("數字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("請輸入一個你要查找的數字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}

分塊查找又索引查找，它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L（一維數組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此，分塊查找的關鍵在於建立索引表A。
（1）建立索引表A（二維數組）
索引表包括兩部分：關鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）
索引表按關鍵字有序的。
例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表：
索引表A：二維數組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，確定待查項X所在的子表（塊）。
（3）在所確定的子表中可以用「折半查找」法搜索待查項X；若找到則輸出X；否則輸出未找到信息。

I. java去公司工作用到的是哪方面的知識

小公司做小項目一般都用SSH+jsp大公司做項目都是根據不同的項目 採取不同的框架技術,比如銀行大部分都用 EJB等

第一：先學習Java的核心庫（JavaSE）

JavaSE的內容包括：環境搭建、基礎語法、面向對象、數組、集合、常用類、IO流、反射機制、網路編程……..

第二：MySQL資料庫

搞定一門資料庫相關的課程，例如：MySQL、Oracle，搞定一個就可以了，目前互聯網公司，例如：京東、阿里等，他們都在使用MySQL，所以建議大家學習MySQL資料庫，小巧輕盈，免費，由於互聯網公司的項目訪問量比較大，所以一般會搭建資料庫的集群，可以一個資料庫不夠，所以需要搭建資料庫集群，為了應付高並發。（搭建的比較多的時候，免費就很重要了。）

第三：WEB前端

以後從事Java開發，從事JavaEE開發，主要開發的系統結構是B/S結構的，B指的是Browser，S指的是Server。要開發這種系統，B端要會，S端也要精通。WEB前端的學習就是學習B端技術。包括：HTML 、CSS、JavaScript（JS）、jQuery框架（底層對JS進行了封裝）…

第四：WEB後端（JavaWEB）

WEB後端其實可以是很多種不同的編程語言，例如：PHP、C、C++、Java，他們都可以進行WEB後端的開發，我們既然選擇了比較火爆的Java，那麼我們學習的後端一定是基於Java語言實現的，包括：Servlet、Filter、Jsp、EL、JSTL、MVC架構模式、資料庫連接池（阿里巴巴的Druid連接池）、代理模式（動態代理）。另外後端學習了之後，還要學習一個非同步編程技術AJAX。（完成網頁的局部刷新，AJAX其實不屬於後端，是前端瀏覽器上的程序。）

學習到這里為止，表示Java基本/基礎的技術已經學完了。但是這些最基層的技術在實際的開發中不會使用的，一般為了開發效率，都會使用大量的提前封裝好的框架。

第五：最好能夠停留下來，做一個項目。

這個項目最好能將之前所學全部串起來。（對以前的知識點進行鞏固。）

這個項目最好是基於：Servlet + Jsp+AJAX+jQuery+MySQL….

在這個項目的開發過程中：大家一定要記住，目前比較好的項目自動構建工具：Maven是一定要精通的。還有一個就是團隊協作開發：Git/SVN是一定要會用的。（目前使用Git比較多一些。）

第六：學習高級框架

Spring、SpringMVC、MyBatis（持久層框架，這個框架互聯網公司使用比較多，因為互聯網項目需要進行SQL優化，MyBatis的SQL優化很方便，所以大部分都是使用MyBatis）

Struts2（很少使用了，使用這個的肯定是很老的項目）、Hibernate（傳統企業，還有政府等可能會使用Hibernate。）

SpringBoot（新項目大部分使用的都是boot了。所以在項目中遇到還在使用SSM的一般都是遺留項目。）

當你走到這里之後，基本上你可以出山了。（去找工作，8K的薪資應該問題不大，但前提是你學的好。學習的深度夠了，廣度夠了。）

第七：最好能有一個大型項目是使用框架來完成的。

SpringBoot做一個項目。

Spring SpringMVC MyBatis做一個項目。

這個項目最好是找幾個人搭夥做一下。體驗一下團隊協作。（尤其是使用一些協作的工具。怎麼溝通，怎麼寫日報，怎麼開會，怎麼使用Git，等等….）

第八：如果你的薪資想達到15K的話，你可能需要還要學習一些分布式相關的一些技術。

能夠應付高並發的一些技術，例如：分布式框架Dubbo、SpringCloud、MQ、Nginx、Redis…..

java的知識體系構架

....祝 工作順心 哈哈

J. 一道Java二分查找題目 程序運行超時 求解答

圖中這個時間是包含在控制台輸入的時間嗎？