LintCode The first index of target

系统管理员 2023-06-12 09:06 60阅读 0赞

（一）题目描述

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

（二）注意

此题的关键在于，返回的是第一个target 的index。

（三）代码

  1. public int binarySearch(int[] nums, int target) { 
  2.         int left =0,right = nums.length;
  3.         int middle = (left+right)/2;
  4.         while (left<right){ 
  5.             if (nums[middle]<target){ 
  6.                 left = middle+1;
  7.             }else { //nums[middle]>=target
  8.                 right = middle;
  9.             }
  10.         }
  11.         return target==nums[middle] ? middle:-1;
  12.     }

注：
判断相等之后，先不立即返回index，而是修改right指针指向的位置（first index 所以只会在左一半）。

发表评论

表情：
评论列表 （有 0 条评论，60人围观）

还没有评论，来说两句吧...

相关阅读