创新建设资金网站,网站用户建设的设计与实现,校园网站建设管理,网站前台界面模板下载#x1f31e; 题目#xff1a;
#x1f30f;在有序数组A中#xff0c;查找目标值target #x1f30f;如果找到返回索引 #x1f30f;如果找不到返回-1
算法描述解释前提给定一个内含n个元素的有序数组A#xff0c;满足A0A1A2An-1,一个待查值target1设… 题目
在有序数组A中查找目标值target 如果找到返回索引 如果找不到返回-1
算法描述解释前提给定一个内含n个元素的有序数组A满足A0A1A2·······An-1,一个待查值target1设置left0right n - 12如果left right 结束查找没找到3设置mid (left right )/2mid为中间索引4如果target Am设置right mid -1跳到第2步5如果target Am设置left mid 1跳到第2步6如果Am target结束查找找到了
算法实现 public int binarySearch(int[] arr,int target) {int left 0;int right arr.length-1;while(leftright) {int mid (leftright)1;if(target arr[mid]) {right mid - 1;}else if (arr[mid] target) {left mid 1;}else {return mid;}}return -1;}注解 1.为什么while循环条件是leftright而不是leftright 因为当leftright时midleftright可能为我们想要查找的值 2.为什么mid (leftright)1而不是(leftright)/2呢 是无符号右移无符号右移一位相当于除2取整。 不用(leftright)/2原因是当leftright的值超过int类型的正整数最大范围其值就会由正变负 在其他的资料中二分查找与这个代码不一样
✈️ 二分查找的改动版
public static int binarySearch1(int[] arr,int target) {int left0;int right arr.length; //第一处改动while(left right) { //第二处改动int mid (leftright)1;if(target arr[mid]) {right mid; //第三处改动}else if (arr[mid] target) {left mid 1;}else {return mid;}}return -1;}⛵️注解
rightarr.length作为一个边界存在left可能为我们的查找目标但是right一定不是我们要找到的目标
图解演示
查找13
⛽️在Java中其实已经提供了二分查找的方法binarySearch
public class Test {public static void main(String[] args) {int[] arr {1,2,3,4,5,5,6};int target Arrays.binarySearch(arr,3);System.out.println(target);}
}运行结果 2 二分查找对重复元素的处理
重复元素最靠右的元素
说明查找元素为重复元素的话会查找到最右边的重复元素 Returns 找到则返回最靠右索引 找不到返回-1
//重复元素最靠右的元素
public class Test5 {public static int binarySearch2(int[] arr,int target) {int left 0;int right arr.length-1;int cand -1;while (left right) {int mid (left right)1;if(target arr[mid]) {right mid-1;} else if (arr[mid] target) {left mid1;}else {cand mid;left mid1;}}return cand;}
}说明返回target的最右边的索引 Returns 找到则返回最靠右索引 找不到返回小于target最右边的索引 public static int binarySearchRightMost(int[] arr,int target){int left 0;int right arr.length-1;while(left right) {int mid (left right )1;if(target arr[mid]){right mid-1;}else {left mid 1;}}return left-1;}重复元素最靠左的元素
说明查找元素为重复元素的话会查找到最左边的重复元素 Returns 找到则返回最靠左索引 找不到返回-1 public static int binarySearch2(int[] arr,int target) {int left 0;int right arr.length-1;int cand -1;while (left right) {int mid (left right)1;if(target arr[mid]) {right mid-1;} else if (arr[mid] target) {left mid1;}else {cand mid;right mid - 1;}}return cand;}说明 返回target最左边的索引 Returns 找到则返回最靠左索引 找不到返回比target大的最左边索引 public static int binarySearchLeftMost(int[] arr,int target) {int left0;int right arr.length-1;while(left right) {int mid (left right)1;if(target arr[mid]) {right mid - 1;}else {left mid 1;}}return left;}图解
leetcode二分查找题
1️⃣1.给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 ⏩ 链接: 二分查找 提示 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999,9999]之间。 class Solution {public int search(int[] nums, int target) {int i0;int j nums.length-1;while(ij){int m(ij)1;if(targetnums[m]){jm-1;}else if(nums[m]target){im1;}else{return m;}}return -1;}
}2️⃣2.给定一个排序的整数数组 nums 和一个整数目标值 target 请在数组中找到 target 并返回其下标。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 ⏩ 链接: 搜索插入位置
class Solution {public int searchInsert(int[] nums, int target) {int left0;int right nums.length-1;while(left right) {int mid (left right)1;if(target nums[mid]) {right mid - 1;}else {left mid 1;}}return left;}
}3️⃣3.给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 ⏩ 链接: 在排序数组中查找元素的第一个和最后一个位置
class Solution {public int[] searchRange(int[] nums, int target) {int xleft(nums,target);if(x-1){return new int[]{-1,-1};}else{return new int[]{x,right(nums,target)};}}public int left(int[] nums,int target) {int i0;int jnums.length-1;int cand-1;while(ij){int m(ij)1;if(targetnums[m]){jm-1;}else if(nums[m]target){im1;}else{candm;jm-1;}}return cand;}public int right(int[] nums,int target) {int i0;int jnums.length-1;int cand-1;while(ij){int m(ij)1;if(targetnums[m]){jm-1;}else if(nums[m]target){im1;}else{candm;im1;}}return cand;}
}
文章转载自： http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.cknws.cn.gov.cn.cknws.cn http://www.morning.slwfy.cn.gov.cn.slwfy.cn http://www.morning.jfjqs.cn.gov.cn.jfjqs.cn http://www.morning.pzrpz.cn.gov.cn.pzrpz.cn http://www.morning.gzzxlp.com.gov.cn.gzzxlp.com http://www.morning.bqdpy.cn.gov.cn.bqdpy.cn http://www.morning.xppj.cn.gov.cn.xppj.cn http://www.morning.jzlfq.cn.gov.cn.jzlfq.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.ydgzj.cn.gov.cn.ydgzj.cn http://www.morning.fxjnn.cn.gov.cn.fxjnn.cn http://www.morning.mnsmb.cn.gov.cn.mnsmb.cn http://www.morning.sffwz.cn.gov.cn.sffwz.cn http://www.morning.rrms.cn.gov.cn.rrms.cn http://www.morning.dtpqw.cn.gov.cn.dtpqw.cn http://www.morning.jkdtz.cn.gov.cn.jkdtz.cn http://www.morning.qjxkx.cn.gov.cn.qjxkx.cn http://www.morning.fxxmj.cn.gov.cn.fxxmj.cn http://www.morning.rydbs.cn.gov.cn.rydbs.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.rmqlf.cn.gov.cn.rmqlf.cn http://www.morning.djxnw.cn.gov.cn.djxnw.cn http://www.morning.llxqj.cn.gov.cn.llxqj.cn http://www.morning.dnmwl.cn.gov.cn.dnmwl.cn http://www.morning.ktlfb.cn.gov.cn.ktlfb.cn http://www.morning.qllcp.cn.gov.cn.qllcp.cn http://www.morning.qpljg.cn.gov.cn.qpljg.cn http://www.morning.qfplp.cn.gov.cn.qfplp.cn http://www.morning.gzxnj.cn.gov.cn.gzxnj.cn http://www.morning.wbhzr.cn.gov.cn.wbhzr.cn http://www.morning.tkyxl.cn.gov.cn.tkyxl.cn http://www.morning.jjtwh.cn.gov.cn.jjtwh.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.nndbz.cn.gov.cn.nndbz.cn http://www.morning.dqcpm.cn.gov.cn.dqcpm.cn http://www.morning.xtdtt.cn.gov.cn.xtdtt.cn http://www.morning.mlmwl.cn.gov.cn.mlmwl.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.hgsylxs.com.gov.cn.hgsylxs.com http://www.morning.lbzgt.cn.gov.cn.lbzgt.cn http://www.morning.gfrtg.com.gov.cn.gfrtg.com http://www.morning.ptzf.cn.gov.cn.ptzf.cn http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.zcqbx.cn.gov.cn.zcqbx.cn http://www.morning.yfphk.cn.gov.cn.yfphk.cn http://www.morning.ktnmg.cn.gov.cn.ktnmg.cn http://www.morning.dpfr.cn.gov.cn.dpfr.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.tgyzk.cn.gov.cn.tgyzk.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.madamli.com.gov.cn.madamli.com http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn http://www.morning.kxnnh.cn.gov.cn.kxnnh.cn http://www.morning.jpnw.cn.gov.cn.jpnw.cn http://www.morning.rfrnc.cn.gov.cn.rfrnc.cn http://www.morning.yhwxn.cn.gov.cn.yhwxn.cn http://www.morning.twwzk.cn.gov.cn.twwzk.cn http://www.morning.sypby.cn.gov.cn.sypby.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.21r000.cn.gov.cn.21r000.cn http://www.morning.tgdys.cn.gov.cn.tgdys.cn http://www.morning.mgkb.cn.gov.cn.mgkb.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.hxrg.cn.gov.cn.hxrg.cn http://www.morning.pqwrg.cn.gov.cn.pqwrg.cn http://www.morning.rbnp.cn.gov.cn.rbnp.cn http://www.morning.lwcqh.cn.gov.cn.lwcqh.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.yzxhk.cn.gov.cn.yzxhk.cn http://www.morning.fdmtr.cn.gov.cn.fdmtr.cn http://www.morning.jcwrb.cn.gov.cn.jcwrb.cn http://www.morning.mpngp.cn.gov.cn.mpngp.cn http://www.morning.pszw.cn.gov.cn.pszw.cn http://www.morning.tlyms.cn.gov.cn.tlyms.cn http://www.morning.skcmt.cn.gov.cn.skcmt.cn http://www.morning.ltdrz.cn.gov.cn.ltdrz.cn http://www.morning.yqqgp.cn.gov.cn.yqqgp.cn http://www.morning.mwlxk.cn.gov.cn.mwlxk.cn
