1. 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.

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 <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

Approach

• Simple find mid then accordingly assign left and right
• One possibility that when you find mid by using left sum right and both these numbers are close to the constraints in that case the sum can overflow so we can find mid in a different way to avoid it
• First find the distance to reach mid way using right - left / 2 and once you have the distance just add to the left
• In built function also exist in java
• Time:O(logn) Space:O(1)

public class Solution {
    public int search(int[] nums, int target) {
        int index = Arrays.binarySearch(nums, target);
        return index >= 0 ? index : -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
 
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] > target)
                r = m - 1;
            else if (nums[m] < target)
                l = m + 1;
            else
                return m;         
        }
 
        return -1;
    }
}