Leetcode-704-Binary Search

Binary Search

leetcode: https://leetcode.com/problems/binary-search/

Description:

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.

Idea: the defination of the interval is important, each interval is defined with same rule([ ]or[ ):include the right bound or not), each operation in the while loop need consider the defination of interval.

Step1: Because the nums is sorted, if the target less than the first element in the nums or the target bigger than the last one, it doesn’t exist in the string

Step2: set the right,left and mid bound. make the mid bound = right + (left-right)/2

Step3: if the target bigger than middle, make the right bound index to the middle pointer +1, otherwise, make the left bound index to middle index -1;

Code:

class Solution {
    public int search(int[] nums, int target) {
//      because the nums is sorted, if the target less than the first element in the nums or the target bigger than the last one, it doesn't exist in the string
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        
//      set the left bound and right bound
        int i=0;
        int j=nums.length-1;
        
//      set the mid pointer, because it's sorted, so if the middle one bigger than target, then make the left bound equal to middle-1, otherwise make the right bound to the middle+1;
        while(i<=j){
            int mid = i + (j-i)/2;
            if(nums[mid] == target){
                return mid;
            }
            else if(target < nums[mid]){
                j = mid-1;
            }
            else if(target > nums[mid]){
                i = mid+1;
            }
        }
//      this target doesn't exist in the nums
        return -1;
    }
}