binary search using for loop in javascript

Question

I am trying to implement binary search using for loop in javascript but it fails some of the test cases, below is my code

function binarySearch(arr, val){
    let start = 0
    let end = arr.length - 1
    let middle = Math.floor((start + end)/2)

    for(let i = start; i<= end; i++){
        if(val === arr[middle]) { 
           return middle
        }

        if(val < arr[middle]){
            end = middle - 1
        }

        if(val > arr[middle]){
           start = middle + 1
        }

        middle = Math.floor((start + end)/2)
    }
        return -1
  }

    // test case:1 console.log(binarySearch([5, 6, 9, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 9))
    
    
   // test case:2 console.log(binarySearch([1,3,4,5,6,7,8,9, 10], 10))

It passes the 2nd test case but miserably fails the 1st one. Can anyone throw some light, please?

Looks like you have a typo. val > middle should be val > arr[middle]. — Ouroborus
– Ouroborus, Commented Oct 11, 2021 at 17:18
@Ouroborus while your suggestion is correct but the problem is still going to persist. I realized why not use "for loop" in this case. It is because inside the loop I'm assigning start a new value but problems arise when you realize that the value of "i" remains the same initially initialized start value. The same occurs with i <= end. I mean "i" is not reassigned anything other than i++. I've realized the fact that under these situations better go with while loop iteration. — Nishant Kumar
– Nishant Kumar, Commented Oct 11, 2021 at 17:53

Nishant Kumar · Accepted Answer · 2021-10-11 18:02:29Z

1

I realized why not use "for loop" in this case.

It is because inside the loop I'm assigning "start" a new value but problems arise when you come across the fact that the value of "i" remains the same previously initialized "start" value.

The same occurs with, i <= end

I mean "i" is not reassigned anything other than i++. I've realized the fact that under these situations it's better to go with the while loop iteration instead of for loop where you need to reinitialize index from inside the loop.

edited Oct 11, 2021 at 18:02

answered Oct 11, 2021 at 17:54

Nishant Kumar

1,0153 gold badges17 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

3limin4t0r Over a year ago

You can use a for-loop if you want, but you'll have to structure it differently. gist.github.com/3limin4t0r/283eb9fa223fe8b6835c1cd9e3e9726c

don · Accepted Answer · 2021-10-15 17:56:02Z

1

Just like you said Nishant, a While-loop would be suitable in this case, because you should update the values of left(start), right(end) and middle indexes inside the loop.

Iterative implementation of Binary Search (in Java):

public int binarySearch(int[] array, int target) {
    var left = 0;
    var right = array.length - 1;

    while (left <= right) { 
        var middle = (left + right) / 2;

        if (array[middle] == target)
            return middle;

        if (target < array[middle]) 
            right = middle - 1;
        else
            left = middle + 1;
    }

    return -1;
}

answered Oct 15, 2021 at 17:56

don

1341 silver badge10 bronze badges

Comments

Adith K · Accepted Answer · 2023-04-16 14:48:52Z

0

public class BinarySearch {

public static int findElement(int[] arr,int target){

    int start=0;
    int end=arr.length-1;

    for(int i=start; i<=end;i++ ){
        int mid=start+(end-start)/2;
        if(arr[mid]==target){
            return mid;
        }else if(arr[mid]<target){
            start=mid+1;
        }else if(arr[mid]>target){
            end=mid-1;
        }
    }
    return -1;
}

public static void main(String [] ar){

    int [] arr={5, 6, 9, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99};

    int target=9;

    int index=findElement(arr,target);

    if(index==-1){
        System.out.println("Element not found");
    }else{
        System.out.println("Element found at index: "+index);
    }

}

}

edited Apr 16, 2023 at 14:48

answered Apr 16, 2023 at 14:46

Adith K

11 bronze badge

1 Comment

Community Over a year ago

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Itz_Broken_xd · Accepted Answer · 2023-07-21 07:36:16Z

I don't know js but I know Java so I'm presenting my implementation of binary search using for loop as follows:

int bSearch(int arr[],int x) {
   int index = 0;
   for(int i = arr.length >> 1; i >= 1; i>>=1)
       while((index + i < arr.length) && (arr[index + i] <= x)) 
           index+=i;

    return(arr[index] == x) ? index : -1;
}

How it works??

Consider i as mid and index as lower bound of binary search.

If u notice carefully, you'll find that in binary search, everytime the mid starts with arr.length divided by 2 and after every iteration, it gets divided by 2 and a last step, it reaches it's minimum value i.e. 1.

So in for loop I've implemented the same. But those who are wondering what is:

int i = arr.length >> 1;

It actually means:

int i = arr.length / 2;

And same for

i>>=1

It is same as:

i /= 2; or i = i / 2;

Now at the while loop part, the first condition checks that if we add index with i , will it go out of the boundary of array or not. The second condition checks whether x lies in between index(lower bound) and i (mid). If it's true then we don't need to add index with i but if it's not the case then :

x lies after i(mid) so we are adding index(lower bound) with i(mid).

This part of code highlighted in traditional binary search:

int bSearch(int arr[], int x) {
int lowerBound = 0;
int upperBound = array.length - 1;

    while (left <= right) { 
        int middle = (lowerBound + upperBound) / 2;

        if (array[middle] == x)
            return middle;
        
        // *look at this condition carefully*

        if (x > array[middle])
            lowerBound = middle + 1; 
        else
            upperBound = middle - 1;
    }

    return -1;
}

Notice the following line:

if(x > arr[middle])
  lowerBound = middle + 1;

The above code can be also written as:

if(arr[middle + lowerBound] <= x)
   lowerBound += middle;

Now if x is present in the array and array is sorted then index should have the index of x and return it else otherwise, it will return -1.

Collectives™ on Stack Overflow

binary search using for loop in javascript

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related