Home > Java > javaTutorial > Analysis of Java ordered array data structure and binary search algorithm

Analysis of Java ordered array data structure and binary search algorithm

黄舟
Release: 2017-09-25 10:18:11
Original
2042 people have browsed it

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;
   }
}
Copy after login

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();
   }
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template