十大算法之二分查找

package com.atguigu.binarysearchnorecursion;public class BinarySearchNoRecur {public static void mainString[] args) {//测试int[] arr = {1,3, 8, 10, 11, 67, 100};int index = binarySearcharr, 100);System.out.println"index=" + index);//}//二分查找的非递归实现/*** * @param arr 待查找的数组, arr是升序排序* @param target 需要查找的数* @return 返回对应下标，-1表示没有找到*/public static int binarySearchint[] arr, int target) {int left = 0;int right = arr.length - 1;whileleft <= right) { //说明继续查找int mid = left + right) / 2;ifarr[mid] == target) {return mid;} else if  arr[mid] > target) {right = mid - 1;//需要向左边查找} else {left = mid + 1; //需要向右边查找}}return -1;}}

class Solution{public int serchint[]nums,int target){int len=nums.length;//判空且长度iflen==0){return -1;int left=0;int right=len-1;//确认左右边界whileleft <=right){//左边界小于右边界int mid=left+right)/2;//中间值ifnums[mid]==target){//如果中间值等于目的值return mid;}else ifnums[mid]<target){left=mid+1;}else{right=mid;}}return left;}}}

class Solution {public int[] searchRangeint[] nums, int target) {int[] res = {-1, -1};if nums == null || nums.length == 0) return res;int leftMost = findFirstOccurrencePosnums, target);if leftMost == -1) {return res;}int rightMost = findLastOccurrencePosnums, target);res[0] = leftMost;res[1] = rightMost;return res;}private int findFirstOccurrencePosint[] nums, int target) {int l = 0, r = nums.length - 1;while l + 1 < r) {int mid = l + r - l) / 2;if nums[mid] >= target) r = mid;else l = mid;}if nums[l] == target) return l;if nums[r] == target) return r;return -1;}private int findLastOccurrencePosint[] nums, int target) {int l = 0, r = nums.length - 1;while l + 1 < r) {int mid = l + r - l) / 2;if nums[mid] <= target) l = mid;else r = mid;}if nums[r] == target) return r;return l;}
}