day 1 of 365-day leetcode challenge to understand programming languages and DSA concepts

day 1. Problem 704 binary search.md

Binary Search

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

Problem

We are given a sorted array of integers nums (ascending order).
Write a function that searches for target in nums.

• If target exists, return its index
• Otherwise, return -1
• The algorithm must run in O(log n) time

---

Key Insight

Because the array is sorted, we can use binary search.

Instead of scanning both halves, we:

• Repeatedly discard half of the search space
• Compare the middle element to the target
• Narrow the search range accordingly

---

Thought Process

1. Set two pointers: low and high
2. While low <= high:
   • Compute mid
   • If nums[mid] == target, return mid
   • If nums[mid] < target, search the right half
   • Otherwise, search the left half
3. If the loop ends, the target is not present → return -1

complexity

• time O(log n)
• space O(1)

func search(nums []int, target int) int {
    low, high := 0, len(nums)-1
    for low <= high {
        mid := low + (high - low)/2
        if nums[mid] ==  target {
            return mid
        }
        if nums[mid] > target{
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}