Problem : Easy

LeetCode: 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.

Thought

To solve this problem, first of all is to understand the given constraint:

• All the integers in nums are unique.
• nums is sorted in ascending order.
• Binary Search works best if it is a sorted array and there are only unique numbers and this makes searching the target number easy.

Steps:

• Calculate the middle index to half the array repeatedly. To do this we have to figure out the lowest and highest index of the array first.
• We use the middle index to control which part of the array it traversing of. MiddleIndex = lowIndex + (highIndex-lowIndex)/2
• In a while loop, when lowIndex and highIndex meets, break. The Final middle index is the index of the target value.
• If the target value doesn’t exists, return -1 outside the while loop.

Solution: Java

class Solution {

    public int search(int[] nums, int target) {
        int mid = 0;
        int low = 0;
        int high = nums.length-1;
        while(low<=high)
        {
            mid = low + ( high - low ) / 2;
            if(target==nums[mid])
                return mid;
            
            else
                if(nums[mid]>target)
                    high = mid-1;
            else
                low = mid+1;
        }
        return -1;
    }
};

For more instructions head over to the LeetCode.