search target in nums array

This problem was asked by Google.

Given an array of sorted integers in ascending order, and a target integer, write a function to search target in nums array. If target exists, return the index of the target in the array, otherwise return -1.

Example

function binarySearch(arr, target){

};

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 5;
console.log(binarySearch(arr, target)); // 4

Solution

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid; 
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Explanation

• Initialize left and right pointers representing search range
• Calculate the middle index
• If middle element matches target, return the index
• If middle element is less than target, update left pointer to mid + 1
• If middle element is greater than target, update right pointer to mid - 1
• Repeat steps 2-5 narrowing search range each iteration
• If target not found, return -1
• This implements a classic binary search algorithm to efficiently search a sorted array in O(log n) time complexity. The array is continuously divided in half after each comparison, eliminating half of the elements until the target is found.