二分查找

package com.zyx.Class2;
二分查询 应用于 有序数组。
若数组有序，使用二分查询
二分查询的变种：
如果 一个数组是： arr[] = {1,1,1,1,1,3,5,7,9,11,13,15,15,15,16};
// 找出指定值 第一次出现的位置。
/*
解决方法：
在找到后，加一个while循环，while(arr[middle-1] == arr[middle] ){ middle—; }
*/
public class MiddleSort {
// 二分查询的非递归实现
public static int binarySearchSort(int[] arr, int val) {
int left = 0;
int right = arr.length - 1;
int middle = 0;
while (left <= right) { // 为什么不是 left < right ？
// left和right指向同一个位置，这个区域还有一个值，这个值 我们还没有进行比较。
middle = (right + left) / 2; // (right-left) >>1 + left;
if (arr[middle] < val) {
left = middle + 1;
} else if (arr[middle] > val) {
right = middle - 1;
} else {
return middle;
}
}
return -1;
}

// 二分查询的递归实现
public static int binSearch(int arr[], int left, int right, int val) {
if (left <= right) {
int middle = (left + right) / 2;
if (arr[middle] > val) {
return binSearch(arr, 0, middle - 1, val);
} else if (arr[middle] < val) {
return binSearch(arr, middle + 1, arr.length - 1, val);
} else {
while (middle > left && arr[middle - 1] == val) {
middle—;
}
return middle;
}
}
return -1;
}
public static void main (String[]args){
int arr[] = new int[]{0, 1, 1, 1, 5, 7, 9, 11, 11, 11, 11, 13, 14};
System.out.println(binarySearchSort(arr, 7));
System.out.println(binSearch(arr, 0, arr.length - 1, 11));
}
}