一.链表

单向链表 

/单向链表
public class SinglyLinkedList implements Iterable<Integer> {//头节点private Node head =null;//头指针//节点类private static   class  Node{int value;//值Node next;//下一个节点的指针public Node(int value, Node next) {this.value = value;this.next = next;}}
}

  addFirst方法

 public  void  addFirst(int value){//1.链表为空//  head =new Node(value,null);//2.链表非空head =new Node(value,head

遍历链表 

一 

public  void  loop1(Consumer<Integer> consumer){Node p =head;while (p!=null){consumer.accept(p.value);p=p.next;}}

二 

  public  void  loop2(Consumer<Integer> consumer){for (Node p =head;p!=null;p=p.next){consumer.accept(p.value);}}

 三 

@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {SinglyLinkedList.Node p = head;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic Integer next() {//返回当前值，并指向下一个元素int v = p.value;p = p.next;return v;}};}

 Test类e

 SinglyLinkedList LinkedList = new SinglyLinkedList();LinkedList.addFirst(1);LinkedList.addFirst(2);LinkedList.addFirst(3);LinkedList.addFirst(4);LinkedList.addFirst(5);LinkedList.loop1(value->{System.out.println(value);});System.out.println("------------------------");LinkedList.loop2(value->{System.out.println(value);});//使用迭代器去遍历链表for (Integer value : LinkedList) {System.out.println(value);}}

二分查找 

1.基础版 

 public  static String binarysearch(int []arr, int data){//1.定义两个变量，一个站左边，一个站右边int left=0;int right=arr.length-1;while (left<=right){int middle=(left+right)/2;if (data<arr[middle]){right=middle-1;}else if(data>arr[middle]){left=middle+1;}else {return  String.valueOf(middle);}}return "该数组没有该数字";}

1.关于为什么在中间值不使用middle=（left+right）/2；

因为Java中使用 在Java中，进行二分查找时，直接使用 middle = (left + right) / 2 可能会遇到整数溢出的问题。这是因为当 left 和 right 都非常大且接近 Integer.MAX_VALUE 时，它们的和可能会超过 int 类型的最大值，从而导致溢出。

 改进版

int middle = left + (right - left) / 2;

无符号右移一位相当于除以2向下取整 

那么 

int middle = left +right >>> 1; 

2.关于为什么使用left<=right去作为判断跳出循环的条件而不是去用left<right去作为判断的条件 

 如果使用 left < right 作为条件，那么在最后一次迭代中，当 left 和 right 相邻时（即 left = right - 1），循环就会提前终止，从而可能错过目标元素（如果它正好位于 left 或 right 指向的位置）。

 left ==right 意味着它们指向的元素也会参与比较，left < right  只意味着middle指向的元素参与比较

2.改进版二分查找

public  static String binarysearch(int [] arr,int target){int left =0, right =arr.length;while (left<right){int  middle =left+right >>> 1;if(target<arr[middle]){right=middle;}else if(arr[middle]<target){left =middle +1;}else {return  String.valueOf(middle);}}return "没有找到该数字" ;}

1）令right为arr.length是确定right为数组边界外一值并不是数组中的值不希望right参与比较，在其中left是参加比较的值而right是不参与比较的值

使得在target在小于arr[middle]时令right=middle 

2）关于循环跳出条件为left<right的原因

当查找的数没有在数组中时会进行死循环报错

3.平衡版

问题切入点：

l为总循环次数，当元素在最右边与最左边时的循环次数不一致。在最右边要进行2*l次比较

 

时间复杂度都为log（n）。 

 

  public  static String binarysearch(int [] arr,int target) {int left =0, right=arr.length;while (1<right-left){int middle =(left+right)>>>1;if(target<arr[middle]){right=middle;}else {left=middle;}}if(arr[left]==target){return  String.valueOf(left);}else {return  "没有该数字";}}

4.java版二分查找

 

private static int binarySearch0(long[] a, int fromIndex, int toIndex,long key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;long midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found.}

关于使用Java自身提供的区别在于返回值当查询不到数据时返回的是-（插入值+1） 

return -(low + 1);  // key not found. 

eg  当我的数组为{1，23，45，77，123}时我查找12时就会返回-2（因为12拍数组第二所以-（1+1）=-2）

 int arr2[]={12,14,123,434,56};System.out.println(Arrays.binarySearch(arr2, 13));

返回-2 

5.leftmost与rightmost

实现查找重复数字中最左边序号  

 

  public static int binarySearchLeftMost(int arr[], int target) {int left = 0, right = arr.length - 1;int candidate = -1;while (left <= right) {int middle = (left + right) >>> 1;if (target < arr[middle]) {right = middle - 1;} else if (arr[middle] < target) {left = middle + 1;} else {//记录候选者位置candidate = middle;right = middle - 1; // 继续向左搜索}}return candidate;}

实现查找重复数字中最右边序号  

区别：在边界处不同

// 继续向右搜索，直到找到最右边的位置  
            left = middle + 1;   

 

public static int binarySearchRightMost(int arr[], int target) {  int left = 0, right = arr.length - 1;  int candidate = -1;  while (left <= right) {  int middle = (left + right) >>> 1;  if (target < arr[middle]) {  right = middle - 1;  } else if (arr[middle] < target) {  left = middle + 1;  } else {  candidate = middle;  // 继续向右搜索，直到找到最右边的位置  left = middle + 1;  }  }