This article mainly introduces the detailed explanation of Java data structures and algorithms (ordered arrays and binary search), which has certain reference value. Interested friends can refer to it
1. Overview
Binary search is often used in ordered arrays, which can improve the search speed. Today, we use sequential search and binary search to implement addition, deletion, modification and search of arrays.
2. Advantages and Disadvantages of Ordered Arrays
Advantages: The search speed is much faster than that of unordered arrays
Disadvantages: When inserting, you must sort the following Move the data
3. Common advantages and disadvantages of ordered arrays and unordered arrays
When deleting data, the following data must be moved forward to fill in the deleted items Vulnerability
4. Code implementation
public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默认长度 * * @param max */ public OrderArray(int max){ this.a = new long[max]; nElemes = 0; } //查找方法 (二分查找) public int find(long searchElement){ int startIndex = 0; int endIndex = nElemes-1; int curIn; while(true){ curIn = (startIndex + endIndex)/2; if(a[curIn]==searchElement){ return curIn; //找到 }else if(startIndex>endIndex){ //沒有找到 return nElemes; //返回大于最大索引整数 }else{ //还要继续找 if(a[curIn]<searchElement){ startIndex = curIn + 1; //改变最小索引 }else{ //往前找 endIndex = curIn -1; } } } } //插入元素(线性查找) public void insert(long value){ int j; for(j=0;j<nElemes;j++){ if(a[j]>value){ break; } } for(int k=nElemes;k>j;k--){ a[k] = a[k-1]; } a[j] = value; nElemes++; } //删除数据项 public boolean delete(long value){ int j = find(value); if(j==nElemes){ return false; //没找到 }else{ //所有元素往前移动一位 for(int k=j;k<nElemes;k++) a[k] = a[k+1]; nElemes--; return true; } } //展示的方法 public void display(){ for(int i=0;i<nElemes;i++){ System.out.print(a[i]+" "); } } public int size(){ return nElemes; } }
5. Test
public static void main(String[] args) { int max = 100; OrderArray oa = new OrderArray(max); oa.insert(12); oa.insert(14); oa.insert(90); oa.insert(89); oa.insert(87); oa.insert(88); oa.insert(67); oa.display(); int searchkey = 90; if(oa.find(searchkey)!=oa.size()){ System.out.println("found"+searchkey); }else{ System.out.println("not found"); } oa.delete(88); oa.delete(90); oa.delete(89); oa.display(); }
The above is the detailed content of Analysis of Java ordered array data structure and binary search algorithm. For more information, please follow other related articles on the PHP Chinese website!