704. Binary Search (Solution || Leetcode easy || Java)

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.

SOLUTION:

class Solution {
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length — 1;

while(start <= end){
int mid = start + (end — start)/2;

if(nums[mid] == target){//if we found the target return mid that is the index of target
return mid;
}else if(nums[mid] > target){//if mid is greater than target it means that all the element after mid are greater than target hence we reduce the search space by moving end toward mid
end = mid — 1;
}else{
start = mid + 1;//if mid is less than target it means that all the elements before mid are less than target as the array is sored in ascending order so we move start toward mid
}
}

return -1;
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries, please let me know in the comment section.