对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。
给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。
测试样例：
[1,3,5,7,9],5,3
返回：1
[编程题]二分查找
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int low=0,higth=n,res=-1;
while (low != higth){
int mid = (low + higth)/2;
if (A[mid] > val){
higth = mid;
}else if (A[mid] < val){
low = mid;
if (res != -1){
break;
}
}else {
res = mid;
higth = mid;
}
}
return res;
}
}
发表于 2022-01-25 21:28:45
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int left = 0;
int right = n - 1;
int mid = 0;
while(left <= right){
mid = (left + right) / 2;
if(A[mid] > val){
right = mid - 1;
}else if(A[mid] < val){
left = mid + 1;
}else{
while(mid >= 0){
if(A[mid] != val){
return mid + 1;
}else{
mid --;
}
}
return mid + 1;
}
}
return -1;
}
}
发表于 2020-04-30 09:26:21
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int first = 0, last = n,mid;//n
while(first < last){
if(A[0]==val)
//经过观察，这种写法仅在第一个位置是val时输出错误，所以单独处理
return 0;
mid = first + (last-first)/2;
if(A[mid]<val){
first = mid + 1;
}
else if(A[mid]==val){
return mid;
}
else
last = mid;
}
return -1;
}
}
发表于 2020-04-29 21:28:26
回复(0)
import java.util.*;
public class BinarySearch
{
public int getPos(int[] A, int n, int val)
{
return getIndex(A,0,A.length-1,val);
}
private int getIndex(int [] arr,int left,int right,int target)
{
if(left>right)//说明递归查找完整个数组，还没有找到
{
return -1;
}
int midIndex=(left+right)/2;
int midValue=arr[midIndex];
if(target>midValue)//如果你要找的数比中间的数大，就去右边找
{
return getIndex(arr,midIndex+1,right,target);
}
else if(target<midValue)//如果你要找的数比中间的数小，就去左边找
{
return getIndex(arr,left,midIndex-1,target);
}
else
{
while(midIndex>left&&arr[midIndex-1]==target)
{
midIndex=midIndex-1;
return midIndex;
}
return midIndex;
}
}
}
发表于 2020-03-28 10:02:03
回复(0)
找到第一个比val小的数，res++就是第一个val出现的下标了，如果不是则证明val不存在
public int getPos(int[] A, int n, int val) {
int left=0;
int right=n-1;
int m;
int res=-1;
while(left<=right){
m=(left+right)/2;
if(A[m]<val){
res=m;
left=m+1;
}else{
right=m-1;
}
}
res++;
if(res>=n||A[res]!=val) return -1;
else return res;
}
发表于 2018-08-24 23:59:11
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] a, int n, int value) {
// write code here
int middle;
int left = 0;
int right = n - 1;
while (left <= right) {
middle = (left + right) / 2;
if (a[middle] > value) {
right = middle - 1;
}
else if (a[middle] < value) {
left = middle + 1;
}
else {
//return middle;
//如果出现多次value，
//遍历一下数组a获得第一个value的数组下标返回即可
for (int i = 0; i < n; i++) {
if (a[i] == value) {
return i;
}
}
}
}
return -1;
}
}
发表于 2018-05-26 11:36:05
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int start=0;
int end=A.length;
int mid=(start+end)/2;
while(start<=end) {
if(A[mid]==val) {
return mid;
}
if(A[mid]<val) {
start=mid+1;
}else if(A[mid]>val){
end=mid-1;
}
mid=(start+end)/2;
}
return -1;
}
}
发表于 2018-01-31 11:45:31
回复(0)
二分查找看似简单，其实细节很多。返回第一次出现和最后一次出现，细节有很多。我简单标记一下，自己理解吧。
//指定值第一次出现
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int left = 0;
int right = n-1;
int center =(left+right)/2;
while(left<right){
if(A[center]>=val){//1、为什么这里取等放入
right = center;
}
else{//2、为什么不在这边放置等于的情况
left = center+1;
}
//3、center赋值位置放这和放循环开始处什么区别
//4、当取最后一次出现的位置，我这里一般改成(left+right+1)/2
//5、当取最后一次出现的位置，除了4处修改，对于1、2取等和right left赋值都有些许变化
center = (left+right)/2;
}
return A[center]==val?center:-1;
}
}
编辑于 2017-12-10 22:19:23
回复(0)
二分法,当找到的时候 继续领end=mid，可以求出firstpos 另start=mid 可以求出endpostion
public class BinarySearch { public int getPos(int[] A, int n, int val) { // write code here
int start=0;
int end=A.length-1;
while(start+1<end){ int mid = (start+end)/2;
if(val==A[mid]){ end=mid;
}else if(val>A[mid]){ start=mid;
}else if(val<A[mid]){ end=mid;
}
}
if(A[start]==val){ return start;
}
if(A[end]==val){ return end;
}
return -1;
}
}
发表于 2017-09-12 13:39:00
回复(0)
// Java 典型的 二分查找（递归做法）
public int getPos(int[] A, int n, int val) {
if (A == null || A.length <= 0)
return -1;
return getPos(A, 0, A.length-1, val);
}
private int getPos(int[] A, int low, int high, int val) {
if (low > high)
return -1;
int mid = (low + high) >> 1;
if (A[ mid ] == val && (mid == low || A[ mid - 1 ] != val))
return mid;
else if (A[ mid ] >= val)
return getPos(A, low, mid - 1, val);
else
return getPos(A, mid + 1, high, val);
}
// Java非递归 的二分查找
public int getPos(int[] A, int n, int val) {
if (A == null || A.length <= 0)
return -1;
int mid, low = 0, high = A.length - 1;
while (low <= high) {
mid = (low + high) >> 1;
if (A[ mid ] == val && (mid == low || A[ mid-1 ] != val))
return mid;
else if (A[ mid ] >= val)
high = mid - 1;
else low = mid + 1;
}
return -1;
}
编辑于 2017-08-03 15:56:16
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int start = 0;
int end = n - 1;
boolean flag = false;
while(!flag && start <= end) {
int middle = start + ((end - start) >> 1);
if(A[middle] == val) {
flag = true;
}
else if(A[middle] > val) {
end = middle - 1;
} else {
start = middle + 1;
}
}
if (flag) {
for(int index = 0;index < n;index++) {
if(A[index] == val) {
return index;
}
}
}
return -1;
}
}
注意这里当找到时不能直接返回，而是用一个标志位标志，然后再重新遍历一次数组找到第一次出现 的位置。
发表于 2017-07-22 19:12:42
回复(0)
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
if(n<=0)
return -1;
int res=getk(0,n-1,A,val);
return res;
}
public int getk(int start ,int end ,int[] a,int val)
{
int mid=(start+end)/2;
int num=a[mid];
if(num>val)
{
end=mid;
return getk(0,mid,a,val);
}
else if(num<val)
{
start=mid+1;
return getk(mid+1,end,a,val);
}
else
{
if(mid==0)
return mid;
for(int i=1;i<=mid;i++)
{
if(a[mid-i]==val)
return (mid-i);
else
return mid;
}
}
return -1;
}
}
发表于 2017-07-13 10:00:03
回复(0)
package HaoWeiLai;
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int lo=0, hi=n;
int target =search(A, lo, hi, val);
if(target==n)
return -1;
return A[target] == val? target:-1;
}
public static int search(int[] A, int lo, int hi, int val){
int mid;
while(hi-lo>0){
mid = (lo+hi)>>1;
if(A[mid] < val){
lo = mid+1;
}else if ( val <=A[mid]){
hi = mid;
}
}
return lo;
}
}
编辑于 2017-06-11 00:19:12
回复(2)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int begin = 0;
int end = n-1;
int mid = (begin+end)/2;
while(begin<=end){
if(val>A[mid]){
begin = mid+1;
}else if (val == A[mid]){
if(mid>=1&&val==A[mid-1]){
end = mid-1;
}else {
return mid;
}
}else {
end = mid-1;
}
mid = (begin+end)/2;
}
return -1;
}
}
发表于 2017-05-09 16:13:24
回复(0)
package com.ginto.practise010;
import java.util.Scanner;
public class BinarySearch {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int[] A;
int n;
int val;
System.out.print("输入数组大小：");
n=scanner.nextInt();
A=new int[n];
System.out.print("输入数组元素：");
for(int i=0;i<n;i++){
A[i]=scanner.nextInt();
}
System.out.print("输入需要查找的元素：");
val=scanner.nextInt();
BinarySearch bs=new BinarySearch();
System.out.println(bs.getPos(A, n, val));
}
public int getPos(int[] A, int n, int val) {
int low=0;
int middle;
int high=A.length-1;
while(low<=high){
middle=low+((high-low)>>1);
if(A[middle]==val&&A[low]==A[middle]){
return low;
}else if(A[middle]==val){
return middle;
}else if(A[middle]>val){
high=middle-1;
}else{
low=middle+1;
}
}
return -1;
}
}
发表于 2017-05-08 22:00:29
回复(0)
import java.util.*;
public class Main {
public static int getPos(int[] A, int n, int val) {
int start=0,end=n-1,midNum=-1;public class Main {
public static int getPos(int[] A, int n, int val) {
//Arrays.sort(A);
while(start<=end){
int mid=(start+end)/2;
if(val==A[mid]){
midNum=mid;break;
}
else if(val>A[mid]){
start=mid+1;
}
else end=mid-1;
}
int K=midNum;
if(K!=-1){
for(int i=0;i<n;i++){
if(A[i]==A[K]){
midNum=i; break;
}
}
}
return midNum;
}
}
}
发表于 2017-04-11 15:35:24
回复(0)
只考虑升序的解法如下，降序数组依次类推即可。
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int low = 0;
int high = n;
int mid = 0;
while(low < high){
mid = (low + high)/2;
if(val <= A[mid]){
high = mid;
}else if(val > A[mid]){
low = mid+1;
}
}
if(val == A[low]){
return low;
}else{
return -1;
}
}
}
编辑于 2017-03-31 14:54:20
回复(0)
问题信息
难度：
33条回答
295收藏
46840浏览
通过挑战的用户
查看代码-
2023-01-11 17:21:16 -
2022-11-07 20:15:00
-
2022-11-01 21:33:42 -
2022-10-12 16:33:22
-
2022-10-12 15:26:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
