Leetcode 704

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Constraints: 1 <= nums.length <= 104 -104 < nums[i], target < 104 All the integers in nums are unique. nums is sorted in ascending order.

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left=0;
  4.         int right=nums.length-1;
  5.         int mid;
  6.         int pos=-1;
  7.         while(left<=right){
  8.             mid=left+(right-left)/2;
  9.             if(nums[mid]<target)
  10.                 left=mid+1;
  11.             else if(nums[mid]>target)
  12.                 right=mid-1;
  13.             else{
  14.                 pos=mid;
  15.                 break;
  16.             }
  17.         }
  18.         return pos;
  19.     }
  20. }

Using left<=right is easier to understand.