二分查找

public class BinarySearch {public static int binarySearch(int[] array, int target) {//查找范圍起點int start = 0;//查找范圍終點int end = array.length - 1;//查找范圍中位數int mid;while (start <= end) {//mid=(start+end)/2 有可能溢出mid = start + ((end - start) / 2);if (array[mid] == target) {return mid;} elseif (array[mid] < target) {start = mid + 1;} else {end = mid - 1;}}return -1;}public static void main(String[] args) {int[] array = new int[1000];for (int i = 0; i < 1000; i++) {array[i] = i;}System.out.println(binarySearch(array, 173));} }

跳躍表

import java.util.Random;public class SkipList{//結點“晉升”的概率private static final double PROMOTE_RATE = 0.5;private Node head,tail;private int maxLevel;public SkipList() {head = new Node(Integer.MIN_VALUE);tail = new Node(Integer.MAX_VALUE);head.right = tail;tail.left = head;}//查找結點public Node search(int data){Node p= findNode(data);if(p.data == data){System.out.println("找到結點：" + data);return p;}System.out.println("未找到結點：" + data);return null;}//找到值對應的前置結點private Node findNode(int data){Node node = head;while(true){while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {node = node.right;}if (node.down == null) {break;}node = node.down;}return node;}//插入結點public void insert(int data){Node preNode= findNode(data);//如果data相同，直接返回if (preNode.data == data) {return;}Node node=new Node(data);appendNode(preNode, node);int currentLevel=0;//隨機決定結點是否“晉升”Random random = new Random();while (random.nextDouble() < PROMOTE_RATE) {//如果當前層已經是最高層，需要增加一層if (currentLevel == maxLevel) {addLevel();}//找到上一層的前置節點while (preNode.up==null) {preNode=preNode.left;}preNode=preNode.up;//把“晉升”的新結點插入到上一層Node upperNode = new Node(data);appendNode(preNode, upperNode);upperNode.down = node;node.up = upperNode;node = upperNode;currentLevel++;}}//在前置結點后面添加新結點private void appendNode(Node preNode, Node newNode){newNode.left=preNode;newNode.right=preNode.right;preNode.right.left=newNode;preNode.right=newNode;}//增加一層private void addLevel(){maxLevel++;Node p1=new Node(Integer.MIN_VALUE);Node p2=new Node(Integer.MAX_VALUE);p1.right=p2;p2.left=p1;p1.down=head;head.up=p1;p2.down=tail;tail.up=p2;head=p1;tail=p2;}//刪除結點public boolean remove(int data){Node removedNode = search(data);if(removedNode == null){return false;}int currentLevel=0;while (removedNode != null){removedNode.right.left = removedNode.left;removedNode.left.right = removedNode.right;//如果不是最底層，且只有無窮小和無窮大結點，刪除該層if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){removeLevel(removedNode.left);}else {currentLevel ++;}removedNode = removedNode.up;}return true;}//刪除一層private void removeLevel(Node leftNode){Node rightNode = leftNode.right;//如果刪除層是最高層if(leftNode.up == null){leftNode.down = head;leftNode.down.up = null;rightNode.down.up = null;}else {leftNode.up.down = leftNode.down;leftNode.down.up = leftNode.up;rightNode.up.down = rightNode.down;rightNode.down.up = rightNode.up;}maxLevel --;}//輸出底層鏈表public void printList() {Node node=head;while (node.down != null) {node = node.down;}while (node.right.data != Integer.MAX_VALUE) {System.out.print(node.right.data + " ");node = node.right;}System.out.println();}//鏈表結點類public class Node {public int data;//跳表結點的前后和上下都有指針public Node up, down, left, right;public Node(int data) {this.data = data;}}public static void main(String[] args) {SkipList list=new SkipList();list.insert(50);list.insert(15);list.insert(13);list.insert(20);list.insert(100);list.insert(75);list.insert(99);list.insert(76);list.insert(83);list.insert(65);list.printList();list.search(50);list.remove(50);list.search(50);} }

總結

以上是生活随笔為你收集整理的《漫画算法2》源码整理-3 二分查找 跳跃表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。